Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Binary Tree Level Order Traversal (easy)

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

Try it yourself

Try solving this question here:

.....

.....

.....

Like the course? Get enrolled and start learning!
R

Ray

· 5 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

· a month 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

· 4 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