Vertical Order Traversal of a Binary Tree

Q: What is the time complexity of vertical order traversal of a binary tree?

Sorting all nodes by column, depth and value costs O(n log n) and dominates the O(n) walk. Sorting level by level has the same worst case, because the last level of a full tree holds about half the nodes. The space is O(n) .

HardTree traversal Sorting Hashing

+10

A binary tree is stored in the array root in heap order: the root is at index 0, the children of index i are at 2*i+1 (left) and 2*i+2 (right), -1 marks an empty spot, and the array may end with extra -1 entries.

The root is in column 0; a left child is one column left of its parent, a right child one column right. Return one list per column, from left to right. Inside a column, list nodes top to bottom, and nodes that share a column and a depth in increasing order of value.

Function

verticalTraversal(root: integer-array) → integer-2d-array

rootinteger-array: the tree in heap order, with -1 for an empty spot
Returnsinteger-2d-array: one list of values per column, leftmost column first, each from top to bottom

Constraints

1 ≤ root.length ≤ 32767
Each root[i] is -1 or a value with 0 ≤ root[i] ≤ 5000, and no value appears twice.
root[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 tree has at most 14 levels.

Examples

Input: root = [5, 2, 9, 4, 7, 1, 6]
Output: [[4], [2], [5, 1, 7], [9], [6]]
Explanation: Column 0 holds the root 5, then 7 and 1 two levels down. Those two share column and depth, so 1 comes before 7, even though 7 is further left.

Input: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Output: [[2, 5], [1, 4], [3]]
Explanation: Column -1 holds 2 at depth 1 and 5 at depth 3 (the left child of 4). Column 0 holds the root 1 and 4 at index 4. Column 1 holds only 3.

Input: root = [6, -1, -1]
Output: [[6]]
Explanation: 6 has no children, so the answer has a single column, [6].

Follow-up

Every value is at most 5000. Can you use that to drop the comparison sort and finish in O(n + 5000) time?

Solution

Each node has three keys: column, depth and value. The answer is the nodes ordered by those keys, one list per column. Ties in column and depth go by value, not in the left-to-right order a traversal meets them, so you must sort: every node at once, or each level of a breadth-first search.

Record every node, then sort

Intuition

Visit every node once, in any order, and record the triple (column, depth, value). A step to a child adds 1 to the depth and moves the column 1 left or right. Then sort the triples by column, depth and value. Each column's nodes now sit together, in the required order. Walk the sorted list and start a new inner list whenever the column changes.

In example 1, column 0's triples sort to (0, 0, 5), (0, 2, 1), (0, 2, 7). The sort, O(n log n), dominates the O(n) walk, and the triples take O(n) space.

Algorithm

Push (index 0, column 0, depth 0) on a stack.
Pop a node, record (column, depth, value), and push each real child with column col-1 or col+1 and depth depth+1.
When the stack is empty, sort the triples by column, then depth, then value.
Walk them, starting a new list whenever the column changes.

def verticalTraversal(root):
    n = len(root)
    entries = []  # (column, depth, value) for every node
    stack = [(0, 0, 0)]  # (node index, column, depth); the root is never empty
    while stack:
        i, col, depth = stack.pop()
        entries.append((col, depth, root[i]))
        for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
            if child < n and root[child] != -1:
                stack.append((child, child_col, depth + 1))
    # Column, then depth, then value: exactly the order of the answer.
    entries.sort()
    result = []
    for k, (col, depth, value) in enumerate(entries):
        if k == 0 or col != entries[k - 1][0]:
            result.append([])  # a new column starts
        result[-1].append(value)
    return result

Level by level, sort inside each level

Intuition

A breadth-first search handles one level at a time. If each node appends its value to its column's list when it is handled, every list is already top to bottom, so depth needs no sorting. Ties happen only within one level, so sort each level by column, then value, before handling it.

In example 1, level 2 arrives as 4, 7, 1, 6 in columns -2, 0, 0, 2 and sorts to 4, 1, 7, 6, so column 0 becomes [5, 1, 7]. The occupied columns form one unbroken range, so tracking the smallest and largest is enough.

Sorting a level of m nodes costs O(m log m). The worst case is still O(n log n), because the last level of a full tree holds about half the nodes. The space is O(n).

Algorithm

Start with a level holding (index 0, column 0).
Sort the level by column, then value.
In that order, append each value to its column's list, and collect its real children, with columns col-1 and col+1, into the next level.
Repeat until a level is empty, tracking the smallest and largest column.
Return the lists from the smallest column to the largest.

def verticalTraversal(root):
    n = len(root)
    columns = {}  # column -> its values, top to bottom
    level = [(0, 0)]  # (node index, column) of every node on the current level
    while level:
        # Every node here has the same depth: order them by column, then value.
        level.sort(key=lambda node: (node[1], root[node[0]]))
        next_level = []
        for i, col in level:
            columns.setdefault(col, []).append(root[i])
            for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
                if child < n and root[child] != -1:
                    next_level.append((child, child_col))
        level = next_level
    # The columns that hold a node form one unbroken range.
    return [columns[col] for col in range(min(columns), max(columns) + 1)]

Pitfalls and edge cases

Leaving ties in left-to-right order. A breadth-first search without the per-level sort gives [5, 7, 1] for column 0 of example 1, not [5, 1, 7].
Appending values during a depth-first walk with no sort. In [1, 2, 3, -1, 4, -1, -1, -1, -1, -1, 5], a left-first walk appends 5 (depth 3) to column 1 before 3 (depth 1).
Sorting by column and value but not depth. Column 0 of example 1 then reads [1, 5, 7].
Keying the columns by strings. Sorted as text, "-1" comes before "-2", so the columns left of 0 come out in the wrong order.

Frequently asked questions3

What is the time complexity of vertical order traversal of a binary tree?

Sorting all nodes by column, depth and value costs O(n log n) and dominates the O(n) walk. Sorting level by level has the same worst case, because the last level of a full tree holds about half the nodes. The space is O(n).

Can vertical order traversal be done without sorting?

Only if ties go in left-to-right order. Then a breadth-first search that appends each value to its column's list gives the answer in O(n). With ties ordered by value you need some sorting, but only within a level, since only nodes on one level can tie.

How does vertical order traversal relate to the top view and the bottom view?

All three group nodes by the same column numbers. The top view keeps each column's shallowest node and the bottom view its deepest. Vertical order traversal keeps every node, and when several share a level it orders them by value, while the views pick by position.

def verticalTraversal(root):
    # Write code here

Test #1

Test #2

Test #3

Argument

root = [5, 2, 9, 4, 7, 1, 6]

Expected Output

[[4], [2], [5, 1, 7], [9], [6]]