DSA sheet · Trees · BFS pattern

Top View of Binary Tree

This video introduces one new idea that the next few problems (Bottom View, Vertical Order Traversal) are built on: horizontal distance, a "column number" for every node. Once each node has a column number, the top view is simply the first node we meet in each column, going from top to bottom. The teacher solves it twice: first with BFS (a queue), where it is very natural, then with DFS (recursion), where we discover that we also need to carry the level, and she shows a tree that breaks the code if we forget it.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Horizontal distance, explained slowly
• Part A · Top View with BFS
• Part B · Top View with DFS (and why we need the level)
• Part C · Revision page

Part 0 · Before starting: horizontal distance

Words we will use

The x-axis picture the teacher uses

Think of the root sitting at 0 on a number line (the x-axis). Moving left takes you to the negative numbers, moving right takes you to the positive numbers.

   left ←   -3   -2   -1    0   +1   +2   +3   → right
                             ↑
                           root

So the rule for children is always the same, no matter how deep we are:

This is the same trick the teacher used in level order traversal with DFS, where every child got "parent's level + 1". There we counted rows. Here we count columns in the same way.

Working out HD on the teacher's tree

Here is the main tree of the video. The number in brackets is the HD of each node.

                  1 (0)
              /          \
         2 (-1)           3 (+1)
         /    \           /    \
     4 (-2)   6 (0)    7 (0)   8 (+2)
         \                        \
         5 (-1)                    9 (+3)

1. Root 1 → HD 0.
2. 2 is the left child of 1 → 0 − 1 = −1. 3 is the right child of 1 → 0 + 1 = +1.
3. 4 is the left child of 2 → −1 − 1 = −2. 6 is the right child of 2 → −1 + 1 = 0.
4. 7 is the left child of 3 → +1 − 1 = 0. 8 is the right child of 3 → +1 + 1 = +2.
5. 5 is the right child of 4 → −2 + 1 = −1. 9 is the right child of 8 → +2 + 1 = +3.

Now put every node in a grid: columns are HD, rows are levels. This is what the tree "really" looks like from the side.

Reading each column from top to bottom:

• HD −2: 4
• HD −1: 2, then 5 (5 is under 2, so hidden)
• HD 0: 1, then 6 and 7 (both under 1, hidden)
• HD +1: 3
• HD +2: 8
• HD +3: 9

The top of each column, from left to right, is 4 2 1 3 8 9. That is exactly the expected top view. So the teacher's plan is: give every node its HD, group nodes by HD, and keep only the first (highest) node of each group.

"Why not just use DFS or BFS and print the corner nodes?"

The teacher first asks whether a normal traversal can solve this on its own.

• A plain DFS or BFS visits every node. It has no way to know that 5, 6 and 7 should be skipped.
• A tempting idea: "the top view is just the outer nodes, the left side plus the right side". On this tree the left view is 1, 2, 4, 5 and the right view is 1, 3, 8, 9. Joining them would include 5. But 5 is hidden under 2 (both have HD −1). So corner nodes are wrong.
• The real reason: top view is about vertical columns. Level order groups nodes by rows. We need a way to group by columns, and that is exactly what HD gives us.

The two examples from the problem statement

       1 (0)
      /    \
  2 (-1)   3 (+1)

               10 (0)
            /         \
       20 (-1)        30 (+1)
       /    \         /    \
  40 (-2) 60 (0)  90 (0)  100 (+2)

In Example 2, 60 and 90 both land in column 0, under 10. From the top, 10 covers them, so they don't appear in the answer.

Part A · Top View with BFS

GFG · Top View of Binary Tree

1The question in simple words

You get the root of a binary tree. Return the list of node values you would see if you looked at the tree from above, ordered from the leftmost column to the rightmost column. In each column, only the highest node is visible.

If two nodes are in the same column and on the same level (like 6 and 7 above), the one further left counts as "first". (Here they are both hidden anyway, because 1 is higher.)

2What the constraints tell us

• Number of nodes: 1 to 10⁵ → the tree is never empty. In BFS we don't strictly need an empty check (we still add one as a safe guard).
• n can be 10⁵. An O(n²) idea would be 10⁵ × 10⁵ = 10¹⁰ operations. The safe limit is about 10⁸ per second. Above that it's risky, and at 10⁹ or 10¹⁰ it will surely give TLE.
• So we must aim for linear time: visit each node a fixed number of times.

3Intuition: why BFS fits perfectly

BFS walks the tree level by level, top to bottom (and left to right inside a level). So the first time BFS reaches a column, it has reached the highest node of that column. Every node that comes later in the same column is lower, so it's hidden.

So we keep a small notebook (a dictionary/map): HD → value. When we pop a node:

• its column is not in the notebook yet → this is the top of that column → write it down;
• its column is already in the notebook → someone above already covers it → do nothing.

4Building the logic from the example

What goes into the queue?

In normal BFS the queue holds just nodes. Now every node also needs its HD, because a node doesn't "know" its own column. Its HD comes from its parent. So the queue holds pairs: (node, hd).

Rule 1: first time we see a column → save it

Pop 1 (HD 0). Column 0 is empty in the notebook → save 0 → 1. Pop 2 (HD −1) → empty → save −1 → 2. Pop 3 (HD +1) → save +1 → 3.

Rule 2: column already seen → skip (never overwrite)

Later we pop 6 (HD 0). Column 0 already holds 1. Because BFS goes level by level, 1 was popped earlier, so 1 is higher than 6. From the top, 1 hides 6. So we must not overwrite. The same happens for 7 (HD 0) and for 5 (HD −1, hidden under 2).

Rule 3: push the children with their new HD

This happens for every popped node, whether or not we saved it. Even a hidden node can have children that stick out, so we must keep exploring below it.

• left child exists → push (node.left, hd − 1)
• right child exists → push (node.right, hd + 1)

The teacher points out that the push lines sit outside the "not in map" if. If you put them inside, the children of hidden nodes (like 6 and 7) would never be explored.

Last step: read the notebook from left to right

The answer must go from the most negative HD to the most positive HD. Java's TreeMap keeps keys sorted by itself. In Python, a normal dict remembers the order we inserted keys, which is not left-to-right (we inserted 0, −1, +1, −2, …). So at the end we go through sorted(first).

5Approach steps

1. Make an empty dictionary first (HD → value) and a queue with (root, 0).
2. While the queue is not empty, pop (node, hd).
3. If hd is not in first, save first[hd] = node.val.
4. Push the left child with hd − 1 and the right child with hd + 1 (only if they exist).
5. After the loop, return the values of first in increasing order of HD.

6Code (Python)

from collections import deque

def topView(root):
    if root is None:                   # safe guard (constraints say n >= 1)
        return []
    first = {}                         # hd -> value of the top node
    queue = deque()
    queue.append((root, 0))            # (node, horizontal distance)

    while queue:
        node, hd = queue.popleft()
        if hd not in first:            # first visit of this column = top
            first[hd] = node.val
        if node.left:                  # children are pushed in ALL cases
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))

    return [first[hd] for hd in sorted(first)]

7Code line by line

8Dry run: watch the queue and the notebook

On the main tree (4 2 1 3 8 9 expected). Each box shows value:hd. Yellow = popped now.

                  1 (0)
              /          \
         2 (-1)           3 (+1)
         /    \           /    \
     4 (-2)   6 (0)    7 (0)   8 (+2)
         \                        \
         5 (-1)                    9 (+3)

The teacher catches herself during the dry run: after popping 3, its children 7 and 8 enter the queue before 5, because 5 is one level deeper. The order above follows that fix.

9Complexity & remember

• Time O(n): every node is pushed once and popped once. (Plus w·log w to sort the w columns at the end, which is small.)
• Space O(n): the queue. For a complete tree, the last level alone has about n/2 nodes, and they can all be in the queue together. The notebook holds one entry per column.

Part B · Top View with DFS

1The question in simple words

Same question as Part A. Now we use recursion instead of a queue.

2What the constraints tell us

• n ≥ 1, but in DFS we always need the if node is None: return base case anyway. The function keeps calling itself on children, and sooner or later it reaches a missing child. That base case is the only thing that stops the recursion.
• Linear time is still the target (n up to 10⁵).

3Intuition: what's easier, and what breaks

Easier: in BFS we needed pairs because a queue slot holds one thing. In DFS, the function can simply take extra parameters: dfs(node, level, hd). No pair is needed.

What breaks: DFS does not go top to bottom. It dives down the whole left subtree first, then comes back for the right. So "the first node I saw in this column" is not always the highest one. A deep node on the left can claim a column before a higher node on the right gets there.

The fix: remember how high the saved node was. Save [value, level] per column, and if a new node in that column has a smaller level (it's higher), replace the old one.

First try: copy the BFS rule into DFS (no level)

On the main tree, preorder DFS visits 1, 2, 4, 5, 6, 3, 7, 8, 9:

• 1 (HD 0) → save. 2 (−1) → save. 4 (−2) → save. 5 (−1) → already has 2, skip. 6 (0) → skip.
• 3 (+1) → save. 7 (0) → skip. 8 (+2) → save. 9 (+3) → save.

Answer 4 2 1 3 8 9: it works here by luck. So why does the teacher insist on passing the level? She draws a second tree.

4Building the condition from the tricky example

                 1 (0)        level 0
              /      \
         2 (-1)       9 (+1)  level 1
         /    \
     4 (-2)   3 (0)           level 2
                 \
                 5 (+1)       level 3
                    \
                    6 (+2)    level 4

Look at column +1: it holds 9 (level 1) and 5 (level 3). From the top, 9 is visible, 5 is hidden under it. The correct top view is 4 2 1 9 6.

Now follow DFS with the BFS-style rule "save only if the column is new". DFS goes left first, so it visits 1, 2, 4, 3, 5, 6, and only then 9:

1. 1 → column 0 new → save 1. 2 → column −1 new → save 2. 4 → column −2 new → save 4.
2. 3 → column 0 already has 1 → skip. 5 → column +1 is new → save 5. 6 → column +2 new → save 6.
3. Finally the right side: 9 → column +1 already has 5 → skip.

Result 4 2 1 5 6 ✗. The deep 5 grabbed column +1 first only because DFS reached it first, even though 9 is two levels higher.

The fix: compare levels

So for each column we store two numbers: the value and the level it was found on. When a node arrives in a column that's already taken:

• its level is smaller (it's higher up) → it's the new top → overwrite;
• otherwise → it's lower (or level with it) → keep the old one.

With this rule, when 9 (level 1) arrives at column +1, it sees 5 stored with level 3. 1 < 3 → overwrite with 9. Result 4 2 1 9 6 ✓.

5Approach steps

1. Make an empty dictionary best (HD → [value, level]).
2. Call dfs(root, level=0, hd=0).
3. In dfs: if the node is None, return.
4. If hd is new, save [node.val, level]. Else, if level is smaller than the saved level, overwrite.
5. Recurse left with (level + 1, hd − 1) and right with (level + 1, hd + 1).
6. After DFS, return the saved values sorted by HD.

6Code (Python)

def topView(root):
    best = {}                          # hd -> [value, level]

    def dfs(node, level, hd):
        if node is None:               # base case: stops the recursion
            return
        if hd not in best:             # column seen for the first time
            best[hd] = [node.val, level]
        elif level < best[hd][1]:      # this node is HIGHER than the saved one
            best[hd] = [node.val, level]
        dfs(node.left, level + 1, hd - 1)
        dfs(node.right, level + 1, hd + 1)

    dfs(root, 0, 0)
    return [best[hd][0] for hd in sorted(best)]

7Code line by line

8Dry run with the call stack

On the tricky tree (1 → 2, 9; 2 → 4, 3; 3 → right 5; 5 → right 6). Each call is written as value(level, hd).

1. 1(0, 0): column 0 new → best = {0: [1, 0]}. Go left.
2. 2(1, −1): column −1 new → save [2, 1]. Go left.
3. 4(2, −2): column −2 new → save [4, 2]. Its children are None → both calls return at once. 4 leaves the stack.
4. Back in 2, go right: 3(2, 0): column 0 holds [1, 0]. Is 2 < 0? No → keep 1. Left child None. Go right.
5. 5(3, +1): column +1 new → save [5, 3]. Go right.
6. 6(4, +2): column +2 new → save [6, 4]. No children → return. Then 5, 3 and 2 return one by one.
7. Back in 1, go right: 9(1, +1): column +1 holds [5, 3]. Is 1 < 3? Yes → overwrite with [9, 1].
8. 9 has no children → return. 1 returns. Stack empty.
9. best = {0:[1,0], −1:[2,1], −2:[4,2], +1:[9,1], +2:[6,4]} → sorted by HD → [4, 2, 1, 9, 6] ✓

The newest call is on top (red). On the main tree the same code gives 4 2 1 3 8 9, exactly like BFS.

9Complexity & remember

• Time O(n): each node is visited once (plus sorting the columns at the end).
• Space: the call stack is as tall as the tree. The stack only ever holds one node per level on the current path, so about log n for a balanced tree and n for a skewed tree. The dictionary has one entry per column. Its size is the width of the tree from the leftmost to the rightmost column.

Part C · Revision page

main = TreeNode(1,
         TreeNode(2, TreeNode(4, None, TreeNode(5)), TreeNode(6)),
         TreeNode(3, TreeNode(7), TreeNode(8, None, TreeNode(9))))
tricky = TreeNode(1,
           TreeNode(2, TreeNode(4), TreeNode(3, None, TreeNode(5, None, TreeNode(6)))),
           TreeNode(9))
print(topView(main))      # [4, 2, 1, 3, 8, 9]
print(topView(tricky))    # [4, 2, 1, 9, 6]
print(topView(TreeNode(1, TreeNode(2), TreeNode(3))))   # [2, 1, 3]

Based on this video: Top View of Binary Tree | BFS & DFS