DSA sheet · Trees · BFS pattern

Bottom View of Binary Tree

This is the twin of Top View, and the teacher says clearly that Top View is the prerequisite. We use the same column numbers (horizontal distance) and the same BFS and DFS code. Only one line changes in each version: in BFS we stop guarding against overwriting, and in DFS we flip the comparison sign. The interesting part is understanding why such a small change gives the opposite view, and how ties are broken.

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 · Quick recap of horizontal distance
• Part A · Bottom View with BFS
• Part B · Bottom View with DFS
• Part C · Revision page

Part 0 · Before starting: horizontal distance again

Level = how far down a node is (root = level 0, children = level 1, …). Horizontal distance (HD) = how far left or right of the root a node is. The teacher also calls it the "vertex" or "vertical level".

   left ←   -2   -1    0   +1   +2   → right      (root sits at 0)

Top view = the highest node in each column. Bottom view = the lowest node in each column. Picture lying under the tree and looking up: the deepest node in each column blocks everything above it.

The teacher's tree, with HD in brackets

Some values repeat in this tree, so the two 4's are called 4a and 4b, and the two 5's 5a and 5b.

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

1. 1 → 0. Its left 2 → −1, its right 9 → +1.
2. 2's left 4a → −2. 2's right 3 → −1 + 1 = 0.
3. 4a's right 5a → −2 + 1 = −1. 3's left 4b → 0 − 1 = −1. 3's right 5b → 0 + 1 = +1.
4. 5b's right 6 → +1 + 1 = +2.

Read each column from the bottom: −2 → 4a, −1 → (5a and 4b are tied at level 3), 0 → 3, +1 → 5b (9 is above it, hidden), +2 → 6. 1 and 9 are not visible from below.

The tie: two nodes in the same column and the same level

5a and 4b are both at HD −1 and level 3. They sit exactly on the same spot. Which one do we report? The problem says: take the later one in level order, i.e. the one further right. The teacher points to the problem's own example to show this:

                20 (0)
             /        \
         8 (-1)        22 (+1)
         /    \        /     \
    5 (-2)  3 (0)   4 (0)   25 (+2)
            /   \
       10 (-1)  14 (+1)

3 and 4 are both at HD 0, level 2. The expected answer is 5 10 4 14 25, so 4 (the one on the right, seen later) wins, not 3. In our tree that means 4b wins over 5a (4b comes after 5a in level order).

So the bottom view of the teacher's tree is 4 4 3 5 6 (4a, 4b, 3, 5b, 6).

Part A · Bottom View with BFS

GFG · Bottom View of Binary Tree

1The question in simple words

Given the root, return the values seen when looking at the tree from below, from the leftmost column to the rightmost. In each column, the lowest node is visible. If two nodes share the lowest spot (same column, same level), report the one that comes later in level order (the right one).

2What the constraints tell us

• Same as Top View: 1 to 10⁵ nodes. The tree is never empty (we keep a guard anyway).
• 10⁵ nodes rules out O(n²) (10¹⁰ operations is far beyond the ~10⁸ safe limit). We want O(n).

3Intuition: just keep overwriting

BFS goes level by level, top to bottom. So within one column, the nodes come out of the queue from highest to lowest, and for equal levels, from left to right.

• Top View wanted the first node of each column → "save only if new".
• Bottom View wants the last node of each column → save every time, so each later node overwrites the earlier one. When BFS ends, the value left in each column is the lowest one.

The teacher's line: "Why are you even checking whether the column is there? Simply keep putting it."

4Building the logic from the example

Follow column 0 in the teacher's tree. BFS meets 1 (level 0) first, then 3 (level 2).

• Pop 1 → column 0 = 1.
• Pop 3 → overwrite column 0 with 3. Correct: 3 is below 1, so from the bottom you see 3.

Column +1: pop 9 (level 1) → +1 = 9. Later pop 5b (level 3) → overwrite with 5b. Correct: 5b is lower.

Column −1: pop 2 → 2. Then at level 3, BFS pops 5a first (it's a child of 4a, which is further left), then 4b → the final value is 4b. That matches the tie rule ("the later one wins") for free.

5Approach steps

1. Queue starts with (root, 0). Dictionary last is empty.
2. Pop (node, hd). Write last[hd] = node.val, always.
3. Push left child with hd − 1, right child with hd + 1.
4. When the queue is empty, return last's values in increasing HD order.

6Code (Python)

from collections import deque

def bottomView(root):
    if root is None:                   # safe guard (constraints say n >= 1)
        return []
    last = {}                          # hd -> value of the lowest node so far
    queue = deque()
    queue.append((root, 0))

    while queue:
        node, hd = queue.popleft()
        last[hd] = node.val            # ONLY CHANGE: always overwrite
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))

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

7Code line by line

8Dry run: queue and notebook

Teacher's tree. Boxes show value:hd.

9Complexity & remember

• Time O(n): each node goes in and out of the queue once (plus sorting the columns).
• Space O(n): the queue can hold a whole level (about n/2 nodes in a complete tree).

Part B · Bottom View with DFS

1The question in simple words

Same question. Now with recursion, passing level and hd as parameters.

2What the constraints tell us

• DFS always needs if node is None: return. It is what stops the recursion at missing children, even though the tree itself is never empty.
• Python note: a skewed tree with 10⁵ nodes means 10⁵ nested calls, beyond Python's default limit of about 1000. Use sys.setrecursionlimit or the BFS version for such inputs.

3Intuition: "always overwrite" is wrong in DFS

In BFS, "later" meant "lower". In DFS, "later" only means "visited later", and DFS visits the whole left side before the right side. So a higher node on the right can arrive after a deeper node on the left.

Look at column +1 in the teacher's tree. DFS visits 1, 2, 4a, 5a, 3, 4b, 5b, 6 and only then 9. If we just overwrite, 9 (level 1) replaces 5b (level 3) and we report 9. But from below, 5b hides 9. ✗

So, just like Top View DFS, we save [value, level] for each column and compare levels before overwriting. This time we want the deeper node, so the sign flips.

4Building the condition from the example

Column new → save

1 at (level 0, HD 0): column 0 is empty → save [1, 0]. Same for 2 → [2, 1] at −1 and 4a → [4, 2] at −2.

Column taken, new node deeper → overwrite

5a arrives at HD −1, level 3. Saved is [2, 1]. 3 > 1, so 5a is lower → overwrite with [5, 3]. Then 3 arrives at HD 0, level 2, and saved is [1, 0]. 2 > 0 → overwrite with [3, 2].

Column taken, same level → overwrite too (this is why it's >=)

4b arrives at HD −1, level 3. Saved is [5, 3]. The levels are equal. The tie rule says the later (right) node wins, and DFS visits the left one first, so the right one is the one arriving now. If we used only >, 5a would stay ✗. With >=, 4b overwrites it ✓.

Column taken, new node higher → keep the old one

9 arrives at HD +1, level 1. Saved is [5, 3] (5b). 1 is not ≥ 3 → keep 5b ✓.

5Approach steps

1. best = {} (HD → [value, level]). Call dfs(root, 0, 0).
2. In dfs: None → return.
3. If the column is new, save. Else if level >= saved level, overwrite.
4. Recurse left (level + 1, hd − 1), then right (level + 1, hd + 1). Left first matters for ties.
5. Return saved values sorted by HD.

6Code (Python)

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

    def dfs(node, level, hd):
        if node is None:               # base case
            return
        if hd not in best:             # first node in this column
            best[hd] = [node.val, level]
        elif level >= best[hd][1]:     # ONLY CHANGE from top view: < became >=
            best[hd] = [node.val, level]
        dfs(node.left, level + 1, hd - 1)     # left first (ties need this order)
        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

Teacher's tree. Calls are written value(level, hd).

1. 1(0,0) → best[0] = [1,0]. Go left.
2. 2(1,−1) → best[−1] = [2,1]. Go left.
3. 4a(2,−2) → best[−2] = [4,2]. Left is None. Go right.
4. 5a(3,−1) → saved [2,1], 3 ≥ 1 → best[−1] = [5,3]. No children → return. 4a returns.
5. Back in 2, go right: 3(2,0) → saved [1,0], 2 ≥ 0 → best[0] = [3,2].
6. 4b(3,−1) → saved [5,3], 3 ≥ 3 → best[−1] = [4,3] (tie, right one wins). Return.
7. 5b(3,+1) → column +1 new → best[+1] = [5,3]. Go right.
8. 6(4,+2) → new → best[+2] = [6,4]. Return. 5b, 3 and 2 return one by one.
9. Back in 1, go right: 9(1,+1) → saved [5,3], 1 ≥ 3? No → keep 5b. Return.
10. best = {0:[3,2], −1:[4,3], −2:[4,2], +1:[5,3], +2:[6,4]} → [4, 4, 3, 5, 6] ✓

9Complexity & remember

• Time O(n): one visit per node (plus sorting the columns).
• Space: call stack O(height): log n if balanced, n if skewed. Plus one dictionary entry per column.

Part C · Revision page

t = TreeNode(1,
      TreeNode(2,
        TreeNode(4, None, TreeNode(5)),
        TreeNode(3, TreeNode(4), TreeNode(5, None, TreeNode(6)))),
      TreeNode(9))
g = TreeNode(20,
      TreeNode(8, TreeNode(5), TreeNode(3, TreeNode(10), TreeNode(14))),
      TreeNode(22, TreeNode(4), TreeNode(25)))
print(bottomView(t))   # [4, 4, 3, 5, 6]
print(bottomView(g))   # [5, 10, 4, 14, 25]

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