Binary Tree Level Order Traversal

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

Both solutions visit each node once: O(n) time for n nodes. The answer holds n values, so the space is O(n) . Besides that, the queue holds about the widest level and the recursion 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 and take exactly that many nodes. Two other ways work too: keep the current level and the next level in two separate lists, or push a marker into the queue after each level.

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

For this format it works: level d , with the root at 0, fills indexes 2^d-1 to 2^(d+1)-2 , so collect each range's non-empty values until a range has none. Interviews usually pass node objects with pointers instead, and only the queue carries over to that form.

MediumTree traversal Queue

+10

The array tree holds a binary 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 extra -1 entries may trail at the end.

Return the node values level by level: one list per level, from the root down to the deepest level, each with its values from left to right.

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: Index 3 is empty, so 9 has only a right child, 6. The third level is 6, 8, 5, and the 3 at index 9, below 6, is alone on the fourth.

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.

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

Each level must come out as its own left-to-right list. A breadth-first search with a queue visits nodes in that order, and at the start of each round the queue holds exactly one level, so its size says how many nodes to take. A depth-first walk that tracks each node's depth also works.

Depth-first, filed by depth

Intuition

Walk the tree depth-first, passing each node its depth, 0 for the root, and keep one list per depth. A node at depth d appends its value to list d, starting that list if it is the first node seen on its level.

Each list comes out left to right because the walk finishes a node's left subtree before it enters the right one. Of two nodes on one level, the one whose path turns left where the paths split is reached first. In example 1 the visit order 4, 9, 6, 3, 2, 8, 5 fills [4], [9, 2], [6, 8, 5], [3].

Every node is visited once: O(n) time, with recursion as deep as the tree, 14 levels at most.

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

Take a node out of the queue and put its children in, left first. Level d+1 enters only as level d leaves, so the nodes leave level by level, left to right.

To cut that stream into levels, read the queue's size at the start of a round. The previous level is gone and none of the next has arrived, so the queue holds exactly the current level. Take that many nodes into one row; their children wait for the next round. In example 1 the rounds take 1, 2, 3 and 1 nodes.

Every node enters and leaves the queue once: O(n) time. The queue holds about one level, at most 8,192 nodes on the deepest level of a full 14-level tree.

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

Reading the queue's size while you empty it. In while (j < queue.length) the length grows as children arrive, so the next level leaks into the current row.
Adding the right child before the left one, or visiting the right subtree first. Example 1's second level then reads [2, 9].
Skipping the bound check child < n. The deepest nodes' children sit past the end of the array.
Removing from the front of a plain array list, which in many languages shifts the whole queue each time. Use a real queue or a head index.
Treating -1 as a node. It never enters a row or the queue: [7, -1, -1] gives [[7]], not [[7], []].

Frequently asked questions3

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

Both solutions visit each node once: O(n) time for n nodes. The answer holds n values, so the space is O(n). Besides that, the queue holds about the widest level and the recursion 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 and take exactly that many nodes. Two other ways work too: keep the current level and the next level in two separate lists, or push a marker into the queue after each level.

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

For this format it works: level d, with the root at 0, fills indexes 2^d-1 to 2^(d+1)-2, so collect each range's non-empty values until a range has none. Interviews usually pass node objects with pointers instead, and only the queue carries over to that form.

def levelOrder(tree):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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