DSA sheet · Trees · BFS pattern

Vertical Order Traversal

Top View kept the highest node of each column and Bottom View kept the lowest. This problem wants every node of every column, in a strict order. The teacher's plan has three stages, and they're the same for DFS and BFS: (1) walk the tree and write down (column, row, value) for every node, (2) sort that list, (3) cut the sorted list into one group per column. DFS and BFS only differ in stage 1, so she solves it with DFS first, then shows the BFS way to fill the same list.

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 · Columns and rows (horizontal distance and level)
• Part A · Vertical Order with DFS
• Part B · Vertical Order with BFS
• Part C · Revision page

Part 0 · Before starting: every node gets (row, column)

Picture the x-axis again: the root stands on 0, everything to the left is negative, everything to the right is positive.

   left ←   -2   -1    0   +1   +2   → right

The teacher's main tree

Each node is written as value (row, col).

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

1. 1 is the root → row 0, column 0.
2. 6 = left of 1 → row 1, column 0 − 1 = −1. 2 = right of 1 → row 1, column +1.
3. 4 = left of 6 → row 2, column −2. 5 = right of 6 → row 2, column −1 + 1 = 0.
4. 3 = left of 2 → row 2, column +1 − 1 = 0. 8 = right of 2 → row 2, column +2.
5. 7 = left of 5 → row 3, column −1. 9 = right of 5 → row 3, column +1.

Reading each column top to bottom gives [[4], [6, 7], [1, 3, 5], [2, 9], [8]]. Notice 5 and 3: they are both in row 2, column 0. The problem says that in that case we sort them by value, so 3 comes before 5, even though 5 is in the left subtree.

Example 1 from the problem

          3 (0,0)
        /        \
   9 (1,-1)     20 (1,+1)
                /      \
          15 (2,0)    7 (2,+2)

Column −1: [9]. Column 0: [3, 15]. Column +1: [20]. Column +2: [7]. Answer [[9], [3, 15], [20], [7]].

Part A · Vertical Order with DFS

LeetCode 987 · Vertical Order Traversal of a Binary Tree

1The question in simple words

Give each node its (row, column) as in Part 0. Return a list of columns, from the leftmost column to the rightmost. Inside each column, list the nodes from top to bottom (smaller row first). If two nodes are in the same row and same column, put the smaller value first.

2What the constraints tell us

• Number of nodes: the teacher reads it as 0 to 1000. If 0 is allowed, BFS needs an explicit empty-tree check at the start. DFS needs its None base case anyway, because that's what ends the recursion.
• n ≤ 1000 is small. Sorting all n entries (n log n) is easily fast enough.

3Intuition: write it all down, then sort

Unlike Top/Bottom View, we can't keep "one node per column". We need all of them, and in a specific order that depends on three things. So instead of being clever while walking, the teacher's idea is:

• Walk the tree in any order and write every node down as a small record (column, row, value).
• Sort the records. The sort puts them in exactly the order we need.
• Walk the sorted records and start a new group whenever the column changes.

Once you have the records, the traversal order no longer matters. That's why DFS and BFS both work equally well here.

4Building the sort order from the example

Sort key 1: column

We want column −2 first, then −1, 0, +1, +2. So the records must be sorted by column first, smallest first. That's why the column goes in position 0 of each record.

Sort key 2: row

Column −1 has 6 (row 1) and 7 (row 3). We read top to bottom, so 6 must come before 7. So when the columns are equal, sort by row, smallest first.

Sort key 3: value

Column 0 has 1 (row 0), 5 (row 2), 3 (row 2). 1 comes first by row. 5 and 3 are tied on both column and row, so the problem says sort by value → 3, then 5.

Stage 3: cutting the sorted list into columns

After sorting, the records for one column are all next to each other. But we don't know in advance how many records each column has. The teacher's trick: remember the previous column.

• Start with prev_col = -infinity, a value no real column can equal.
• For each record: if its column is different from prev_col, a new column has begun → append a new empty list to the answer and set prev_col to this column.
• Either way, add the value to the last list in the answer (ans[-1], which is Java's ans.get(ans.size() - 1)).

5Approach steps

1. Make an empty list nodes.
2. DFS with (node, row, col): if None return; else append (col, row, node.val), then go left with (row + 1, col − 1) and right with (row + 1, col + 1).
3. Sort nodes (column, then row, then value).
4. Walk the sorted list; open a new sublist when the column changes; append the value to the last sublist.
5. Return the list of sublists.

6Code (Python)

class Solution:
    def verticalTraversal(self, root):
        nodes = []                              # records (col, row, val)

        def dfs(node, row, col):
            if node is None:                    # base case
                return
            nodes.append((col, row, node.val))
            dfs(node.left, row + 1, col - 1)    # left: one row down, one column left
            dfs(node.right, row + 1, col + 1)   # right: one row down, one column right

        dfs(root, 0, 0)
        nodes.sort()                            # column, then row, then value

        ans = []
        prev_col = float('-inf')
        for col, row, val in nodes:
            if col != prev_col:                 # a new column starts here
                ans.append([])
                prev_col = col
            ans[-1].append(val)                 # add to the current (last) column
        return ans

7Code line by line

8Dry run

Stage 1: DFS fills the list

1. 1(row 0, col 0) → add (0, 0, 1). Go left.
2. 6(1, −1) → add (−1, 1, 6). Go left.
3. 4(2, −2) → add (−2, 2, 4). Both children None → return to 6.
4. 6 goes right: 5(2, 0) → add (0, 2, 5). Go left.
5. 7(3, −1) → add (−1, 3, 7). Return. Then 9(3, +1) → add (1, 3, 9). Return.
6. 5 returns, 6 returns. 1 goes right: 2(1, +1) → add (1, 1, 2).
7. 3(2, 0) → add (0, 2, 3). 8(2, +2) → add (2, 2, 8). Everything returns.

Stage 2: sort

Stage 3: group by column

Final: [[4], [6, 7], [1, 3, 5], [2, 9], [8]] ✓

9Complexity & remember

• Time O(n log n). The DFS itself is O(n), one visit per node. But the list has n records, and sorting n records costs n log n. The bigger term wins. (The teacher first says O(n), then corrects herself in the BFS section: it's the sort that makes it n log n.)
• Space: the recursion stack holds one node per level of the current path, so about log n for a complete tree and n for a skewed tree. On top of that, the records list always has n entries, so the total extra space is O(n).

Part B · Vertical Order with BFS

Stages 2 and 3 (sort and group) are exactly the same as Part A. Only stage 1, filling the records list, changes: we use a queue instead of recursion.

1The question in simple words

Same as Part A.

2What the constraints tell us

• If the tree can have 0 nodes, BFS needs if root is None: return [] at the top. Otherwise we'd push None into the queue and crash when reading .left.

3Intuition

Normal level order traversal, but each queue entry carries three things: the node, its row and its column. When we pop an entry, we write its record, then push its children with their new row and column.

4The changes from DFS

• The queue holds tuples (node, row, col). The teacher needs a Pair class with three fields in Java. Python doesn't.
• Push a child only if it exists: left → (row + 1, col − 1), right → (row + 1, col + 1).

5Approach steps

1. If root is None, return [].
2. Queue starts with (root, 0, 0).
3. While the queue isn't empty: pop, append (col, row, val) to nodes, push existing children.
4. Sort and group exactly as in Part A.

6Code (Python)

from collections import deque

class Solution:
    def verticalTraversal(self, root):
        if root is None:                        # needed in BFS if 0 nodes allowed
            return []
        nodes = []                              # records (col, row, val)
        queue = deque()
        queue.append((root, 0, 0))              # (node, row, col)

        while queue:
            node, row, col = queue.popleft()
            nodes.append((col, row, node.val))
            if node.left:
                queue.append((node.left, row + 1, col - 1))
            if node.right:
                queue.append((node.right, row + 1, col + 1))

        nodes.sort()                            # same as DFS from here on
        ans = []
        prev_col = float('-inf')
        for col, row, val in nodes:
            if col != prev_col:
                ans.append([])
                prev_col = col
            ans[-1].append(val)
        return ans

7Code line by line (only the new lines)

8Dry run: the queue

Main tree. Boxes show value(row,col).

Notice that BFS added 5 before 3 (5 is further left in row 2). The value key in the sort swaps them back into 3, 5.

9Complexity & remember

• Time O(n log n): O(n) for BFS, n log n for sorting n records.
• Space O(n): the queue (up to a whole level) plus the n records.

Part C · Revision page

t = TreeNode(1,
      TreeNode(6, TreeNode(4), TreeNode(5, TreeNode(7), TreeNode(9))),
      TreeNode(2, TreeNode(3), TreeNode(8)))
ex1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
s = Solution()
print(s.verticalTraversal(t))     # [[4], [6, 7], [1, 3, 5], [2, 9], [8]]
print(s.verticalTraversal(ex1))   # [[9], [3, 15], [20], [7]]

Based on this video: Vertical Order Traversal | BFS & DFS