Interview Bootcamp

0% completed

​

Solution: Binary Tree Level Order Traversal

Problem Statement

Given a binary tree, populate an array to represent its level-by-level traversal. You should populate the values of all nodes of each level from left to right in separate sub-arrays.

Example 1:

Example 2:

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000

Solution

Since we need to traverse all nodes of each level before moving onto the next level, we can use the Breadth First Search (BFS) or Level Order traversal technique to solve this problem.

.....

.....

.....

Like the course? Get enrolled and start learning!
R

Ray

· 4 years ago

For JS, you don't need collections/deque. You can shift/push/etc on a regular array.

Satya Pandya

Satya Pandya

· 3 years ago

the code compiler accepts even when I am completely wrong sometimes without displaying anything for input case output or expected output. Same code compiles with proper error on leetcode. design guru compiler accepts without displaying anything

vicky S

vicky S

· 23 days ago

What's the difference between level order traversal and breadth first search, they both looks the same yet we seem to have two separate sections ?

R

Richard Yuan

· 4 years ago

For the python solution, is the time complexity mainly taken from the inner for loop? I understand that the inner for loop will have to perform an iteration for each node in the tree, but I am confused on how to factor in the outer 'while queue' loop into the time complexity calculation. Any help would be appreciated!

Show 3 replies
P

Peter

· 4 years ago

Nice solution but I couldn't see the need for currentLevel, surely you can just append straight to result? Maybe this is used for later examples where averages etc. are performed.

P

Pete Stenger

· 4 years ago

The problem specification doesn't clarify that this is a complete tree... which has the level property you are relying on for the size of each level.

Show 2 replies
S

Salah Osman

· 3 years ago

I understand the space is O(n), with the use of the queue and list were returning. Could someone clarify this sentence

"Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level)

Show 1 reply
V

viniciuslopeslps

· 2 years ago

public List<List<Integer>> traverse(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();

    LinkedList<TreeNode> ll = new LinkedList<>();

    ll.add(root);

    int listSize = 0;
    List<Integer> numbers = new ArrayList<>();

    int kids = 0;
    int level = 1;
    while (!ll.isEmpty()) {
        if (listSize == level) {
            result.add(numbers);
            level = level * kids;
            listSize = 0;
            numbers = new ArrayList<>();
            kids = 0;
            continue;
        }


        TreeNode popped = ll.poll();

        numbers.add(popped.val);
        listSize++;

        if (popped.left != null) {
            ll.add(popped.left);
            kids++;
        }

        if (popped.right != null) {
            ll.add(popped.right
L

lejafilip

· 2 years ago

I remember that traversal problems could be solved using recursion. Code looks cleaner but not always it is possible.

P

Pete Stenger

· 2 years ago

  def traverse(self, root):
    result = []
    # TODO: Write your code here
    level = []
    q = [root]

    levelSize = len(q)
    while len(q) > 0:
      node = q.pop(0)
      level.append(node.val)

      if node.left:
        q.append(node.left)

      if node.right:
        q.append(node.right)
      
      if len(level) == levelSize:
        result.append(level)
        level = []
        levelSize = len(q)

    return result