Vertical Order Traversal of Binary Tree in DSA Python - Execution Trace

Concept Flow - Vertical Order Traversal of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for BFS traversal

↓

Pop node from queue

↓

Add node value to map at its horizontal distance

↓

Add left child to queue with hd-1

↓

Add right child to queue with hd+1

↓

Repeat until queue empty

↓

Sort map keys and output nodes in vertical order

Traverse the tree level by level, track horizontal distances, group nodes by these distances, then output groups from left to right.

Execution Sample

DSA Python

def vertical_order(root):
    from collections import deque, defaultdict
    q = deque([(root, 0)])
    hd_map = defaultdict(list)
    while q:
        node, hd = q.popleft()
        hd_map[hd].append(node.val)
        if node.left: q.append((node.left, hd-1))
        if node.right: q.append((node.right, hd+1))
    return [hd_map[k] for k in sorted(hd_map)]

This code performs vertical order traversal by BFS, grouping nodes by horizontal distance.

Execution Table

Step	Operation	Node Visited	Horizontal Distance (hd)	Queue State	hd_map State	Visual Tree State
1	Start BFS	Root (1)	0	[(1,0)]	{}	1(hd=0)
2	Pop node	1	0	[]	{0: [1]}	1(hd=0)
3	Add left child	2	-1	[(2,-1)]	{0: [1]}	1(hd=0) ├─ 2(hd=-1)
4	Add right child	3	1	[(2,-1),(3,1)]	{0: [1]}	1(hd=0) ├─ 2(hd=-1) └─ 3(hd=1)
5	Pop node	2	-1	[(3,1)]	{0: [1], -1: [2]}	2(hd=-1)
6	Add left child	4	-2	[(3,1),(4,-2)]	{0: [1], -1: [2]}	2(hd=-1) └─ 4(hd=-2)
7	Add right child	5	0	[(3,1),(4,-2),(5,0)]	{0: [1], -1: [2]}	2(hd=-1) ├─ 4(hd=-2) └─ 5(hd=0)
8	Pop node	3	1	[(4,-2),(5,0)]	{0: [1], -1: [2], 1: [3]}	3(hd=1)
9	Pop node	4	-2	[(5,0)]	{0: [1], -1: [2], 1: [3], -2: [4]}	4(hd=-2)
10	Pop node	5	0	[]	{0: [1,5], -1: [2], 1: [3], -2: [4]}	5(hd=0)
11	Queue empty	-	-	[]	{-2: [4], -1: [2], 0: [1,5], 1: [3]}	Traversal done
12	Sort keys and output	-	-	-	-	Output: [[4], [2], [1,5], [3]]

💡 Queue is empty, all nodes visited and grouped by horizontal distance.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 10	Final
q (queue)	[(1,0)]	[]	[(3,1)]	[(5,0)]	[]	[]
hd_map	{}	{0: [1]}	{0: [1], -1: [2]}	{0: [1], -1: [2], 1: [3], -2: [4]}	{0: [1,5], -1: [2], 1: [3], -2: [4]}	{-2: [4], -1: [2], 0: [1,5], 1: [3]}

Key Moments - 3 Insights

Why do we use horizontal distance (hd) and how is it assigned?

Horizontal distance starts at 0 for root. Left child gets hd-1, right child hd+1. This groups nodes vertically. See execution_table steps 3,4,6,7 where hd changes for children.

Why use a queue and BFS instead of DFS?

BFS ensures nodes are processed level by level, preserving top-to-bottom order in each vertical. See execution_table steps where nodes are popped in BFS order.

How do we get the final vertical order output?

After traversal, keys in hd_map are sorted from smallest to largest hd, then node lists are output in that order. See execution_table step 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what nodes are in the queue?

A [(3,1), (4,-2), (5,0)]

B [(2,-1), (3,1)]

C [(4,-2), (5,0)]

D []

💡 Hint

Check the 'Queue State' column at step 7 in execution_table.

At which step does the horizontal distance map first include hd = -2?

A Step 4

B Step 6

C Step 9

D Step 10

💡 Hint

Look at 'hd_map State' column and find when key -2 appears.

If the right child of node 1 was missing, how would the final output change?

A [[4], [2], [1,5], [3]]

B [[2], [1,5], [3]]

C [[4], [2], [1,5]]

D [[4], [2], [1], [5], [3]]

💡 Hint

Without right child 3, hd=1 group is empty; check final output in execution_table step 12.

Concept Snapshot

Vertical Order Traversal of Binary Tree:
- Assign horizontal distance (hd) starting 0 at root
- Use BFS with queue to visit nodes level-wise
- For left child hd = parent hd - 1, right child hd = parent hd + 1
- Group nodes by hd in a map
- After traversal, output nodes sorted by hd from left to right

Full Transcript

Vertical order traversal visits nodes of a binary tree grouped by their vertical columns. We start at the root with horizontal distance zero. Using a queue, we do a breadth-first search, adding left children with hd-1 and right children with hd+1. Each node's value is stored in a map keyed by hd. After visiting all nodes, we sort the keys and output the grouped nodes. This ensures nodes are printed column by column from left to right, top to bottom within each column.

Practice

1. What does Vertical Order Traversal of a binary tree mean?

easy

A. Nodes are grouped by their horizontal rows from top to bottom

B. Nodes are visited level by level from top to bottom

C. Nodes are grouped by their vertical columns from left to right

D. Nodes are visited in preorder (root, left, right)

Solution

1. Step 1: Understand vertical columns in a tree

   Vertical order groups nodes by their horizontal distance from the root, called columns.

2. Step 2: Define vertical order traversal

   It means collecting nodes column-wise from leftmost to rightmost column.

3. Final Answer:

   Nodes are grouped by their vertical columns from left to right -> Option C

4. Quick Check:

   Vertical order = group nodes by columns [OK]

Hint: Think columns from left to right for vertical order [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking vertical order is preorder or inorder traversal
• Mixing rows with columns in traversal

2. Which Python data structure is best to store nodes grouped by their vertical columns during vertical order traversal?

easy

A. Dictionary with column as key and list of nodes as value

B. List

C. Set

D. Tuple

Solution

1. Step 1: Identify need to group nodes by column

   We need to map each column number to the nodes in that column.

2. Step 2: Choose data structure for mapping

   A dictionary with column keys and list values is ideal for grouping nodes by column.

3. Final Answer:

   Dictionary with column as key and list of nodes as value -> Option A

4. Quick Check:

   Use dict for column to nodes mapping [OK]

Hint: Use dict to map columns to node lists [OK]

Common Mistakes:

• Using list only without mapping columns
• Using set which loses order
• Using tuple which is immutable

3. What is the output of vertical order traversal for this tree?

    1
   / \
  2   3
 / \   \
4   5   6

medium

A. [[4, 2], [1, 5, 3], [6]]

B. [[4], [2], [1, 5], [3], [6]]

C. [[1], [2, 3], [4, 5, 6]]

D. [[6], [3], [1, 5], [2], [4]]

Solution

1. Step 1: Assign column indices to nodes

   Root 1 is column 0; left child 2 is -1; right child 3 is +1; 4 is -2; 5 is 0; 6 is +2.

2. Step 2: Group nodes by columns and order top to bottom

   Columns: -2:[4], -1:[2], 0:[1,5], 1:[3], 2:[6].

3. Final Answer:

   [[4], [2], [1, 5], [3], [6]] -> Option B

4. Quick Check:

   Group nodes by column indices [OK]

Hint: Assign columns: left -1, right +1 from root [OK]

Common Mistakes:

• Mixing node order within same column
• Ignoring column indices for children
• Grouping nodes by rows instead of columns

4. Identify the bug in this vertical order traversal code snippet:

def vertical_order(root):
    if not root:
        return []
    col_table = {}
    queue = [(root, 0)]
    while queue:
        node, col = queue.pop()
        if col not in col_table:
            col_table[col] = []
        col_table[col].append(node.val)
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    return [col_table[x] for x in sorted(col_table)]

medium

A. Using pop() removes last element, should use pop(0) for BFS

B. Dictionary keys should be strings, not integers

C. Appending node values instead of nodes causes error

D. Missing check for empty tree at start

Solution

1. Step 1: Analyze queue usage for BFS

   Queue should remove elements from front (pop(0)) for BFS, but pop() removes from end (LIFO).

2. Step 2: Identify impact on traversal order

   Using pop() causes DFS-like order, breaking vertical order traversal logic.

3. Final Answer:

   Using pop() removes last element, should use pop(0) for BFS -> Option A

4. Quick Check:

   Use pop(0) for BFS queue [OK]

Hint: Use pop(0) to dequeue for BFS, not pop() [OK]

Common Mistakes:

• Using pop() instead of pop(0) in BFS queue
• Confusing BFS with DFS traversal order
• Not sorting dictionary keys before output

5. Given a binary tree where multiple nodes share the same vertical and horizontal distance, how should vertical order traversal output be ordered?

hard

A. Sort nodes by column only, ignoring row and value

B. Sort nodes by value only, ignoring position

C. Output nodes in insertion order without sorting

D. Sort nodes by their row (top to bottom), then by value ascending if tie

Solution

1. Step 1: Understand tie cases in vertical order

   When nodes share same column and row, order by node value ascending to maintain consistency.

2. Step 2: Define final ordering rule

   Sort nodes first by row (top to bottom), then by value ascending if rows tie.

3. Final Answer:

   Sort nodes by their row (top to bottom), then by value ascending if tie -> Option D

4. Quick Check:

   Row then value sorting for ties [OK]

Hint: Sort by row, then value for nodes sharing position [OK]

Common Mistakes:

• Ignoring row order and sorting only by column
• Not sorting nodes with same position by value
• Outputting nodes in random or insertion order