Binary Tree Level Order Traversal

Q: What is the time complexity of Binary Tree Level Order Traversal?

Both the breadth-first and the depth-first solution visit each node once, so they run in O(n) time for n nodes. The answer itself holds n values, so the space is O(n) . Besides that, the queue holds at most about the widest level, and the recursion at most the height of the tree.

Q: How do you know where one level ends in a breadth-first search?

Read the queue's size at the start of each round. At that moment the queue holds exactly the nodes of one level, so taking out that many nodes takes out the level and nothing more. Two other ways work too: keep the current level and the next level in two separate lists, or push a marker after each level.

Q: Can level order traversal be done with depth-first search?

Yes. Pass each node its depth and append its value to the list for that depth. As long as the walk visits the left subtree before the right one, every list ends up in left-to-right order. It is also O(n) ; breadth-first is the more direct fit because it produces the levels in order.

Q: The array is already stored level by level. Why not read it in slices?

For this format that works: level d occupies indexes 2^d-1 to 2^(d+1)-2 , so you can collect the non-empty values of each range and stop at the first range without any. In an interview, though, the tree usually comes as node objects with left and right pointers and no indexes to slice. The queue-based traversal is what carries over to that form and to variants such as zigzag order or the right side view.

MediumTree traversal Queue

+10

You get a binary tree stored in the array tree. The root sits at index 0, the children of the node at index i sit at 2*i+1 (left) and 2*i+2 (right), -1 marks an empty spot, and the array may end with extra -1 entries.

Return the node values level by level: a list holding the root's value, then a list with the values one level down, from left to right, and so on to the deepest level.

Function

levelOrder(tree: integer-array) → integer-2d-array

treeinteger-array: the tree in heap order, with -1 for an empty spot
Returnsinteger-2d-array: one list of values per level, top level first, each from left to right

Constraints

1 ≤ tree.length ≤ 32767
Each tree[i] is -1 or a value with 0 ≤ tree[i] ≤ 1000.
tree[0] is never -1, so the tree has at least one node.
The array may end with extra -1 entries past the last node.
Both children of an empty spot are empty too, and the depth is at most 14.

Examples

Input: tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Output: [[4], [9, 2], [6, 8, 5], [3]]
Explanation: The root 4 has children 9 and 2 at indexes 1 and 2. Index 3 is empty, so the third level is 6 (index 4, under 9), then 8 and 5 (indexes 5 and 6, under 2). The 3 at index 9 is the left child of 6, alone on the fourth level.

Input: tree = [7, -1, -1]
Output: [[7]]
Explanation: Both children of the root are -1, so the tree is the single node 7 and has one level.

Input: tree = [1, 3, -1, 5, -1, -1, -1]
Output: [[1], [3], [5]]
Explanation: Each node has only a left child: 3 at index 1 and 5 at index 3. Every level holds one value, and the trailing -1 entries add nothing.

+15 hidden tests on Submit

Follow-up

Can you return the levels in zigzag order, the first from left to right, the second from right to left, and so on, without sorting any level?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Every level has to come out as its own list, ordered from left to right. A breadth-first search with a queue visits the nodes in exactly that order. The one extra idea is knowing where a level ends: at the start of each round the queue holds the whole current level and nothing else, so its size tells you how many nodes to take. A depth-first walk also works, as long as it carries each node's depth and goes left before right.

Depth-first, filed by depth

Intuition

First, moving around the array. The left child of index i is at 2i+1 and the right child at 2i+2. A child is missing when its index is past the end of the array or holds -1. In example 1 the children of 9 (index 1) are at indexes 3 and 4, which hold -1 and 6, so 9 has only a right child.

Now walk the tree depth-first and pass each node its depth, 0 for the root. Keep one list per depth. When you reach a node at depth d, append its value to list d; if there are only d lists so far, this is the first node on a new level, so start a new list first.

Why does every level come out from left to right? The walk finishes a node's whole left subtree before it enters the right subtree. Take two nodes on the same level: where their paths from the root split, one goes left and one goes right, and the walk reaches the left one first. In example 1 the order is 4, 9, 6, 3, 2, 8, 5, which fills the lists as [4], [9, 2], [6, 8, 5], [3].

Every node is visited once, so the time is O(n) for n nodes, and the lists hold n values. The recursion is only as deep as the tree, 15 levels at most here. The R version uses an explicit stack instead, pushing the right child before the left one so the left comes off first, then groups the values by depth with split.

Algorithm

Create an empty list of levels.
Visit the root with depth 0.
At node i with depth d, stop if i is past the end or tree[i] is -1.
If there are only d lists, add an empty one. Append tree[i] to list d.
Visit 2i+1, then 2i+2, both with depth d+1.

def levelOrder(tree):
    n = len(tree)
    levels = []

    def visit(i, depth):
        if i >= n or tree[i] == -1:
            return
        if depth == len(levels):  # the first node seen on this level
            levels.append([])
        levels[depth].append(tree[i])
        # Left before right, so every level fills from left to right.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return levels

Breadth-first, one level per round

Intuition

A queue hands values back in the order they went in. Put the root in. Then repeatedly take a node out and put its children in, left child first. Every node of level d+1 enters the queue when its parent on level d leaves it, so all of level d leaves before any of level d+1, and inside a level the nodes leave from left to right.

That gives one stream of values in level order. To cut it into levels, read the queue's size at the start of a round. At that moment the queue holds exactly the current level: the previous level is gone and none of the next level has arrived. Take out that many nodes into one list. The children they add belong to the next round.

In example 1 the queue starts as [4]: take 1 node, row [4], and 9, 2 enter. Take 2 nodes, row [9, 2], and 6, 8, 5 enter. Take 3, row [6, 8, 5], and 3 enters. Take 1, row [3], and the queue is empty.

Every node enters and leaves the queue once, so the time is O(n). The queue holds at most about one level, up to 16384 nodes on the deepest level of a full tree of depth 14. Use a real queue or a head index: taking the first element out of a plain array list shifts every element after it in many languages.

Algorithm

Put the root's index 0 in a queue.
While the queue is not empty, read its size s and start an empty row.
Take out s indexes. For each index i, append tree[i] to the row.
Add 2i+1, then 2i+2, to the queue when the index is inside the array and does not hold -1.
Append the row to the answer and start the next round.

from collections import deque


def levelOrder(tree):
    n = len(tree)
    levels = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        row = []
        for _ in range(len(queue)):  # exactly the nodes of the current level
            i = queue.popleft()
            row.append(tree[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
        levels.append(row)
    return levels

Pitfalls and edge cases

The traversal itself is short. The bugs are in the level boundaries and the empty spots.

Reading the queue's size while you are still emptying it. In a loop like while (j < queue.length) the length grows as children arrive, so the next level leaks into the current row. Read the size once, before the round starts.
Adding the right child before the left one. Every level then comes out from right to left. The same goes for a depth-first walk that visits the right subtree first.
Treating -1 as a value. An empty spot is not a node, so it never enters a row and never enters the queue.
Forgetting the bound check. The children of the deepest nodes can sit past the end of the array, so test child < n before you read tree[child].
Returning empty levels. The trailing -1 entries hold no nodes, so the answer for [7, -1, -1] is [[7]], not [[7], []].

Frequently asked questions4

What is the time complexity of Binary Tree Level Order Traversal?

Both the breadth-first and the depth-first solution visit each node once, so they run in O(n) time for n nodes. The answer itself holds n values, so the space is O(n). Besides that, the queue holds at most about the widest level, and the recursion at most the height of the tree.

How do you know where one level ends in a breadth-first search?

Read the queue's size at the start of each round. At that moment the queue holds exactly the nodes of one level, so taking out that many nodes takes out the level and nothing more. Two other ways work too: keep the current level and the next level in two separate lists, or push a marker after each level.

Can level order traversal be done with depth-first search?

Yes. Pass each node its depth and append its value to the list for that depth. As long as the walk visits the left subtree before the right one, every list ends up in left-to-right order. It is also O(n); breadth-first is the more direct fit because it produces the levels in order.

The array is already stored level by level. Why not read it in slices?

For this format that works: level d occupies indexes 2^d-1 to 2^(d+1)-2, so you can collect the non-empty values of each range and stop at the first range without any. In an interview, though, the tree usually comes as node objects with left and right pointers and no indexes to slice. The queue-based traversal is what carries over to that form and to variants such as zigzag order or the right side view.

Python

def levelOrder(tree):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]

Expected

[[4], [9, 2], [6, 8, 5], [3]]