Binary Tree Vertical Order Traversal

▶

Steps

setup

Initialize queue and column map

Start by placing the root node (3) in the queue with column index 0. The column map is empty initially.

💡 This sets the starting point for BFS and column tracking, anchoring the root at column 0.

Line:

queue = deque([(root, 0)])
col_table = SortedDict()

💡 The root node's column index is the reference point for all other nodes.

fill_cells

Process root node (3) at column 0

Dequeue node 3 with column 0. Add its value to column 0 in the map. Mark node 3 as active.

💡 Processing the root node first populates the map and sets the stage for its children.

Line:

node, col = queue.popleft()
if col not in col_table:
    col_table[col] = []
col_table[col].append(node.val)

💡 Nodes are grouped by their column index in the map as they are processed.

expand

Enqueue left child (9) of node 3 at column -1

Node 3 has a left child 9. Enqueue node 9 with column index 0 - 1 = -1.

💡 Left children are assigned column index one less than their parent, expanding the column map leftwards.

Line:

if node.left:
    queue.append((node.left, col - 1))

💡 Column indices decrease by 1 when moving left, establishing vertical columns.

expand

Enqueue right child (20) of node 3 at column 1

Node 3 has a right child 20. Enqueue node 20 with column index 0 + 1 = 1.

💡 Right children are assigned column index one more than their parent, expanding the column map rightwards.

Line:

if node.right:
    queue.append((node.right, col + 1))

💡 Column indices increase by 1 when moving right, establishing vertical columns.

fill_cells

Process node 9 at column -1

Dequeue node 9 with column -1. Add its value to column -1 in the map. Mark node 9 as active.

💡 Processing node 9 adds it to the leftmost column group.

Line:

node, col = queue.popleft()
if col not in col_table:
    col_table[col] = []
col_table[col].append(node.val)

💡 Nodes are added to their respective columns in BFS order, preserving top-to-bottom order.

expand

Node 9 has no children, no enqueue

Node 9 has no left or right children, so no new nodes are added to the queue.

💡 Leaf nodes do not expand the queue, BFS continues with remaining nodes.

Line:

if node.left:
    queue.append((node.left, col - 1))
if node.right:
    queue.append((node.right, col + 1))

💡 Queue size decreases when leaf nodes are processed, BFS moves forward.

fill_cells

Process node 20 at column 1

Dequeue node 20 with column 1. Add its value to column 1 in the map. Mark node 20 as active.

💡 Processing node 20 adds it to the rightmost column group so far.

Line:

node, col = queue.popleft()
if col not in col_table:
    col_table[col] = []
col_table[col].append(node.val)

💡 Nodes in right columns are processed and added similarly to left and center columns.

expand

Enqueue left child (15) of node 20 at column 0

Node 20 has a left child 15. Enqueue node 15 with column index 1 - 1 = 0.

💡 Left child of node 20 shares column 0, showing multiple nodes can share a column.

Line:

if node.left:
    queue.append((node.left, col - 1))

💡 Column indices can repeat for different nodes, preserving vertical order.

expand

Enqueue right child (7) of node 20 at column 2

Node 20 has a right child 7. Enqueue node 7 with column index 1 + 1 = 2.

💡 Right child of node 20 extends the column map to the rightmost column 2.

Line:

if node.right:
    queue.append((node.right, col + 1))

💡 Column indices expand dynamically as children are added.

fill_cells

Process node 15 at column 0

Dequeue node 15 with column 0. Add its value to column 0 in the map after node 3. Mark node 15 as active.

💡 Node 15 shares column 0 with node 3, showing vertical order includes multiple nodes per column.

Line:

node, col = queue.popleft()
if col not in col_table:
    col_table[col] = []
col_table[col].append(node.val)

💡 Nodes are appended in BFS order, preserving top-to-bottom order within columns.

expand

Node 15 has no children, no enqueue

Node 15 has no children, so no new nodes are added to the queue.

💡 Leaf nodes do not add to the queue, BFS continues with remaining nodes.

Line:

if node.left:
    queue.append((node.left, col - 1))
if node.right:
    queue.append((node.right, col + 1))

💡 Queue shrinks as leaf nodes are processed.

fill_cells

Process node 7 at column 2

Dequeue node 7 with column 2. Add its value to column 2 in the map. Mark node 7 as active.

💡 Node 7 is the only node in the rightmost column 2.

Line:

node, col = queue.popleft()
if col not in col_table:
    col_table[col] = []
col_table[col].append(node.val)

💡 Nodes in new columns are added to the map dynamically.

expand

Node 7 has no children, no enqueue

Node 7 has no children, so no new nodes are added to the queue.

💡 Leaf nodes end the BFS expansion in their branch.

Line:

if node.left:
    queue.append((node.left, col - 1))
if node.right:
    queue.append((node.right, col + 1))

💡 Queue is now empty, BFS traversal is complete.

reconstruct

Construct final vertical order traversal result

Extract the node value lists from the ordered map in column order: -1, 0, 1, 2.

💡 The ordered map keys define the vertical columns from left to right.

Line:

return list(col_table.values())

💡 The final output groups nodes vertically, preserving BFS order within columns.

from collections import deque
from sortedcontainers import SortedDict

def verticalOrder(root):
    if not root:
        return []  # STEP 1: Handle empty tree
    col_table = SortedDict()  # STEP 1: Initialize ordered map
    queue = deque([(root, 0)])  # STEP 1: Initialize queue with root and column 0
    while queue:
        node, col = queue.popleft()  # STEP 2,5,7,10,12: Dequeue node and column
        if col not in col_table:
            col_table[col] = []  # STEP 2,5,7,10,12: Initialize list for new column
        col_table[col].append(node.val)  # STEP 2,5,7,10,12: Append node value to column list
        if node.left:
            queue.append((node.left, col - 1))  # STEP 3,8: Enqueue left child with col-1
        if node.right:
            queue.append((node.right, col + 1))  # STEP 4,9: Enqueue right child with col+1
    return list(col_table.values())  # STEP 14: Return vertical order traversal

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(verticalOrder(root))

📊

Binary Tree Vertical Order Traversal - Watch the Algorithm Execute, Step by Step

Watching this step-by-step BFS with column tracking reveals how vertical order traversal groups nodes by their horizontal distance from the root, which is hard to grasp from code alone.

3920157

BFS Queue

N0 (L0)

Current node: 0

3920157

3920157

BFS Queue

N1 (L1)

3920157

BFS Queue

N1 (L1)N2 (L1)

Current node: 1

3920157

BFS Queue

N2 (L1)

3920157

BFS Queue

N2 (L1)

Current node: 2

3920157

3920157

BFS Queue

N3 (L2)

3920157

BFS Queue

N3 (L2)N4 (L2)

Current node: 3

3920157

BFS Queue

N4 (L2)

3920157

BFS Queue

N4 (L2)

Current node: 4

3920157

3920157

3920157

Result: [9, 3,15, 20, 7]

Return: [[9],[3,15],[20],[7]]

Key Takeaways

✓ BFS traversal with column tracking groups nodes by vertical columns while preserving top-to-bottom order.

This insight is difficult to see from code alone because the interplay between BFS order and column indices is subtle.

✓ Column indices decrease by 1 when moving left and increase by 1 when moving right, dynamically expanding the column map.

Visualizing column index changes clarifies how vertical columns are assigned and why nodes appear in certain groups.

✓ Multiple nodes can share the same column index, and BFS order ensures they are listed top to bottom within that column.

Seeing nodes appended in BFS order within columns helps understand why vertical order traversal preserves node order.

Practice

1. Consider the following code snippet for finding the minimum depth of a binary tree using BFS. Given the tree below, what is the value of depth when the first leaf node is dequeued? Tree structure: - Root (1) - Left child (2) - Right child (3) - Left child (4)

from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minDepth(root):
    if not root:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:
            return depth
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3, TreeNode(4))
print(minDepth(root))

easy

A. 1

B. 4

C. 3

D. 2

Solution

1. Step 1: Trace the BFS queue operations

   Initially queue = [(root(1), 1)]. Dequeue root: not leaf, enqueue left(2,2) and right(3,2).

2. Step 2: Dequeue next node and check leaf

   Dequeue (2,2). Node 2 has no children, so it is a leaf. Return depth = 2.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First leaf found at depth 2 -> correct BFS behavior [OK]

Hint: First leaf found at depth 2 in BFS traversal [OK]

Common Mistakes:

• Returning depth 1 because root is counted incorrectly
• Continuing BFS past first leaf node
• Confusing node values with depth

2. What is the time complexity of the iterative DFS solution that uses a stack to count good nodes in a binary tree with n nodes and height h?

medium

A. O(n log n) due to repeated max value comparisons

B. O(nh) because max value must be tracked along paths of length h

C. O(n) because each node is visited once and max value updates are O(1)

D. O(h) since only the height of the tree affects traversal

Solution

1. Step 1: Identify number of node visits

   Each node is pushed and popped exactly once from the stack, so O(n) visits.

2. Step 2: Analyze max value update cost

   Updating max_val is a constant time operation per node, no extra traversal per node.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal with constant work per node [OK]

Hint: Each node processed once, max_val update O(1) [OK]

Common Mistakes:

• Assuming max_val tracking adds O(h) per node
• Confusing recursion stack space with time
• Thinking max_val comparisons cause O(n log n)

3. Identify the bug in the following code snippet that attempts to find the bottom-left tree value using BFS:

from collections import deque

class Solution:
    def findBottomLeftValue(self, root):
        queue = deque([root])
        node = None
        while queue:
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return node.val

What is the bug in this code?

medium

A. Appending left child before right child causes the last node to be the bottom-right, not bottom-left.

B. Not initializing node before the loop causes a runtime error if root is None.

C. Returning node.val instead of queue[-1].val returns the wrong node value.

D. Using deque instead of list causes inefficient queue operations.

Solution

1. Step 1: Analyze enqueue order

   The code enqueues left child before right child, so BFS processes nodes left to right at each level.

2. Step 2: Identify last node popped

   Because left child is enqueued first, the last node popped is the bottom-right node, not bottom-left.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Right-to-left insertion is needed to get bottom-left node last [OK]

Hint: Order of child insertion in BFS affects which node is last popped [OK]

Common Mistakes:

• Assuming left-first enqueue gives bottom-left node
• Confusing last popped node with first node at last level
• Thinking deque is inefficient for BFS

4. Examine the following code snippet for level order traversal of an N-ary tree. Which line contains a subtle bug that causes incorrect grouping of nodes by level?

medium

A. Line with 'if not root: return []'

B. Line with 'level_nodes.append(node.val)'

C. Line with 'current_level.append(child) # Bug here'

D. Line with 'current_level, next_level = next_level, deque()'

Solution

1. Step 1: Identify how children are enqueued

   Children should be added to next_level queue, not current_level, to separate levels.

2. Step 2: Understand consequence of bug

   Appending children to current_level causes mixing nodes of different levels in the same queue, breaking level grouping.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct BFS uses separate queues for current and next level [OK]

Hint: Children must be enqueued in next_level, not current_level [OK]

Common Mistakes:

• Appending children to current_level instead of next_level

5. Consider the following buggy code snippet for connecting next right pointers in a perfect binary tree. Which line contains the subtle bug that can cause incorrect next pointer connections?

medium

A. Line: head.left.next = head.right

B. Line: if head.next:

C. Line: leftmost = leftmost.left

D. Line: head.right.next = head.next.right

Solution

1. Step 1: Compare the buggy line with the correct logic

   The correct connection is head.right.next = head.next.left, but here it uses head.next.right, which is incorrect.

2. Step 2: Understand the impact

   This causes right child's next pointer to point to the wrong node, breaking the chain.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Right child's next must connect to next node's left child [OK]

Hint: Right child's next points to next node's left child [OK]

Common Mistakes:

• Confusing next.left and next.right
• Skipping null checks
• Not updating leftmost pointer