Top View of Binary Tree

Q: What is the time complexity of the top view of a binary tree?

A breadth-first search visits each of the n nodes once with an O(1) map lookup per node, so it runs in O(n) time if you track the smallest and largest column. An ordered map of columns makes it O(n log w) for w columns.

MediumTree traversal Hashing

+10

You get a binary tree stored in the array root in heap order: the root at index 0, the children of index i at 2*i+1 (left) and 2*i+2 (right), and -1 for an empty spot.

The root is in column 0; a left child sits one column left of its parent and a right child one column right. From above you see the shallowest node of each column; on a tie, the one first in its level from left to right (the smaller index). Return the values you see, from the leftmost column to the rightmost.

Function

topView(root: integer-array) → integer-array

rootinteger-array: the tree in heap order, with -1 for an empty spot
Returnsinteger-array: the value seen from above in each column, leftmost column first

Constraints

1 ≤ root.length ≤ 32767
Each root[i] is -1 or a value with 0 ≤ root[i] ≤ 10⁴, 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, 9, 6]
Explanation: From left to right the columns hold 4 (column -2), 2 (-1), the root 5 (0), 9 (1) and 6 (2). 7 and 1 also sit in column 0, but the root is above them.

Input: root = [1, 2, -1, -1, 3, -1, -1, -1, -1, -1, 4]
Output: [2, 1, 4]
Explanation: 2 is in column -1. Its right child 3 at index 4 is back in column 0, under the root, so it is hidden. 4 at index 10, the right child of 3, is alone in column 1.

Input: root = [6, -1, -1]
Output: [6]
Explanation: Indexes 1 and 2 hold -1, so 6 stands alone in column 0 and is the whole view.

Follow-up

With node objects instead of an array, there is no index to settle a tie. How would you state the tie rule, and does your breadth-first code change?

Solution

Each column shows its shallowest node, and on a tie the one first in level order. That is exactly the order in which a breadth-first search visits nodes, so the first node the search meets in a column is the answer. A depth-first walk works too, but it has to track depths and break ties with care.

Depth-first, shallowest node per column

Intuition

Walk the tree depth-first with each node's column and depth, and keep, per column, the depth and value of the shallowest node found so far.

Replace only on a strictly smaller depth. Of two tied nodes, the one first in level order is reached first by a walk that explores every left subtree before the matching right one, because where the two paths part it goes left. Replacing on an equal depth lets the later node win: with index 3 empty and nodes at indexes 19 and 23, both sit in column -2 at depth 4, and the answer is the node at index 19.

The occupied columns form one unbroken range, since a node in column -3 has ancestors in columns -1 and -2, so track the smallest and largest column. Each node is visited once, O(n) time, and the recursion is about h calls deep.

Algorithm

Visit the root with column 0 and depth 0. Return at once from an index outside the array or holding -1.
If the column has no node yet, or this depth is strictly smaller than the stored one, store this depth and value.
Visit 2i+1 with column col-1, then 2i+2 with column col+1, one level deeper.
Return the stored values from the smallest column to the largest.

def topView(root):
    n = len(root)
    best = {}  # column -> (depth, value) of the shallowest node found so far

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace only on a strictly smaller depth: on a tie, the node
        # met first is the one further left, which comes first in level order.
        if col not in best or depth < best[col][0]:
            best[col] = (depth, root[i])
        visit(2 * i + 1, col - 1, depth + 1)
        visit(2 * i + 2, col + 1, depth + 1)

    visit(0, 0, 0)
    # The columns that hold a node form one unbroken range.
    return [best[col][1] for col in range(min(best), max(best) + 1)]

Breadth-first, first node per column

Intuition

A queue that takes the root, then each node's left child and then its right child, releases the nodes in level order: every node of depth d before any node of depth d+1, and each level from left to right. That is the problem's priority, so the first node a column receives is the one seen from above, and every later one is skipped.

Each node costs one map lookup, O(n) in total. The queue can hold a whole level, up to about half the nodes, so the space is O(n).

Algorithm

Put the pair (index 0, column 0) in a queue.
Take out a pair (i, col). If the map has no entry for col, store root[i] there.
Add (2i+1, col-1), then (2i+2, col+1), for each child that exists.
When the queue is empty, return the map's values from the smallest column to the largest.

from collections import deque


def topView(root):
    n = len(root)
    top = {}  # column -> value of the first node seen in that column
    queue = deque([(0, 0)])  # (node index, column); the root is never empty
    while queue:
        i, col = queue.popleft()
        # The queue hands out shallower nodes first, and left before right
        # on one level, so the first node of a column is the one seen from above.
        if col not in top:
            top[col] = root[i]
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and root[left] != -1:
            queue.append((left, col - 1))
        if right < n and root[right] != -1:
            queue.append((right, col + 1))
    # The columns that hold a node form one unbroken range.
    return [top[col] for col in range(min(top), max(top) + 1)]

Pitfalls and edge cases

Keeping the first node a depth-first walk finds. If the root's left child has a right child with a right child (column 1, depth 3), the walk meets it before the root's right child (column 1, depth 1).
Queueing the right child first: ties go to the wrong node.
Sorting the columns as text: "-1" sorts before "-2".
Assuming the left subtree fills the negative columns. In example 2 the node 4 is in the root's left subtree and in column 1.

Frequently asked questions3

What is the top view of a binary tree?

Number the columns from the root at 0, one to the left for a left child and one to the right for a right child. The top view lists, for each column from left to right, the node closest to the root.

What is the time complexity of the top view of a binary tree?

A breadth-first search visits each of the n nodes once with an O(1) map lookup per node, so it runs in O(n) time if you track the smallest and largest column. An ordered map of columns makes it O(n log w) for w columns.

How is the top view different from the left view and the bottom view?

The left view picks the first node of each level. The top view picks the shallowest node of each column. The bottom view picks the deepest node per column, so a breadth-first search for it overwrites each column instead of keeping the first node.

def topView(root):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

[4, 2, 5, 9, 6]