Vertical Order Traversal of Binary Tree in DSA C++ - 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 horizontal distance

↓

If left child exists

↓

Push left child with hd-1

↓

If right child exists

↓

Push right child with hd+1

↓

Repeat until queue empty

↓

Extract map entries in order

↓

Output vertical order traversal

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

Execution Sample

DSA C++

struct Node {
  int val;
  Node* left;
  Node* right;
};

void verticalOrder(Node* root) {
  // BFS with horizontal distance tracking
}

This code performs a breadth-first traversal of the binary tree, tracking each node's horizontal distance to group nodes vertically.

Execution Table

Step	Operation	Node Visited	Horizontal Distance (hd)	Queue State (node, hd)	Map State (hd: [nodes])	Visual State
1	Start	Root (1)	0	[(1,0)]	{0: []}	Root node 1 at hd=0
2	Pop from queue	1	0	[]	{0: [1]}	Visited 1, map[0] = [1]
3	Push left child	2	-1	[(2,-1)]	{0: [1]}	Left child 2 at hd=-1
4	Push right child	3	1	[(2,-1),(3,1)]	{0: [1]}	Right child 3 at hd=1
5	Pop from queue	2	-1	[(3,1)]	{0: [1], -1: [2]}	Visited 2, map[-1] = [2]
6	Push left child	4	-2	[(3,1),(4,-2)]	{0: [1], -1: [2]}	Left child 4 at hd=-2
7	Push right child	5	0	[(3,1),(4,-2),(5,0)]	{0: [1], -1: [2]}	Right child 5 at hd=0
8	Pop from queue	3	1	[(4,-2),(5,0)]	{0: [1], -1: [2], 1: [3]}	Visited 3, map[1] = [3]
9	Push left child	6	0	[(4,-2),(5,0),(6,0)]	{0: [1], -1: [2], 1: [3]}	Left child 6 at hd=0
10	Push right child	7	2	[(4,-2),(5,0),(6,0),(7,2)]	{0: [1], -1: [2], 1: [3]}	Right child 7 at hd=2
11	Pop from queue	4	-2	[(5,0),(6,0),(7,2)]	{0: [1], -1: [2], 1: [3], -2: [4]}	Visited 4, map[-2] = [4]
12	Pop from queue	5	0	[(6,0),(7,2)]	{0: [1,5], -1: [2], 1: [3], -2: [4]}	Visited 5, map[0] = [1,5]
13	Pop from queue	6	0	[(7,2)]	{0: [1,5,6], -1: [2], 1: [3], -2: [4]}	Visited 6, map[0] = [1,5,6]
14	Pop from queue	7	2	[]	{0: [1,5,6], -1: [2], 1: [3], -2: [4], 2: [7]}	Visited 7, map[2] = [7]
15	End	None	None	[]	{-2: [4], -1: [2], 0: [1,5,6], 1: [3], 2: [7]}	Traversal complete, output vertical order

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

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 12	After Step 14	Final
Queue	[(1,0)]	[]	[(3,1)]	[(4,-2),(5,0)]	[(6,0),(7,2)]	[]	[]
Map	{}	{0: [1]}	{0: [1], -1: [2]}	{0: [1], -1: [2], 1: [3]}	{0: [1,5], -1: [2], 1: [3], -2: [4]}	{0: [1,5,6], -1: [2], 1: [3], -2: [4], 2: [7]}	{-2: [4], -1: [2], 0: [1,5,6], 1: [3], 2: [7]}

Key Moments - 3 Insights

Why do we use a queue with horizontal distance instead of just a normal queue?

Because we need to know each node's horizontal distance to group nodes vertically. The queue stores pairs (node, hd) so we can track and update the map correctly as shown in execution_table steps 3,4,6,7,9,10.

Why do nodes with the same horizontal distance appear in the order they are visited?

Because we use BFS traversal, nodes are visited level by level. So nodes at the same horizontal distance are added to the map in the order they appear in the queue, as seen in steps 12 and 13 where nodes 5 and 6 both have hd=0.

What happens if the tree is empty?

The queue starts empty, so the loop never runs and the map remains empty. The traversal ends immediately as shown by the exit_note.

Visual Quiz - 3 Questions

Look at the execution_table at step 12, what is the map state for horizontal distance 0?

A [1, 5]

B [1, 5, 6]

C [5, 6]

D [1]

💡 Hint

Check the 'Map State' column at step 12 in execution_table

At which step does the queue become empty, ending the traversal?

A Step 14

B Step 15

C Step 13

D Step 2

💡 Hint

Look at the 'Queue State' column and 'Exit Note' in execution_table

If the left child of node 3 was missing, how would the map change at step 10?

A No node added at hd=0 at step 9

B No node added at hd=2 at step 10

C No node added at hd=1 at step 8

D No change in map

💡 Hint

Check steps 9 and 10 where left and right children of node 3 are pushed

Concept Snapshot

Vertical Order Traversal of Binary Tree:
- Use BFS with a queue storing (node, horizontal distance)
- Start root at hd=0
- Left child hd = parent hd - 1
- Right child hd = parent hd + 1
- Group nodes by hd in a map
- Output map entries from smallest to largest hd
- Nodes at same hd appear in BFS order

Full Transcript

Vertical Order Traversal visits nodes of a binary tree grouped by their horizontal distance from the root. We start at the root with horizontal distance zero. Using a queue, we do a breadth-first search, storing each node with its horizontal distance. For each node visited, we add its value to a map keyed by horizontal distance. Left children have hd one less than their parent, right children one more. After visiting all nodes, we output the nodes grouped by horizontal distance from leftmost to rightmost. This method ensures nodes are output vertically and in top-to-bottom order within each vertical line.

Practice

1. What does vertical order traversal of a binary tree mean?

easy

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

B. Nodes are visited in inorder (left, root, right)

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

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

Solution

1. Step 1: Understand vertical order traversal concept

   Vertical order traversal groups nodes by their vertical columns, where nodes in the same vertical line share the same horizontal distance from the root.

2. Step 2: Compare with other traversals

   Level order visits nodes by depth, preorder and inorder are depth-first traversals, not grouped by vertical columns.

3. Final Answer:

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

4. Quick Check:

   Vertical order = group by vertical columns [OK]

Hint: Vertical order groups nodes by vertical columns [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking preorder or inorder is vertical order
• Ignoring horizontal distance concept

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

easy

A. std::vector<int>

B. std::queue<int>

C. std::map

D. std::stack<int>

Solution

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

   We need a structure that maps vertical column indices (integers) to lists of node values.

2. Step 2: Choose appropriate C++ container

   std::map maps column indices to vectors of node values, maintaining sorted order of columns automatically.

3. Final Answer:

   std::map -> Option C

4. Quick Check:

   Map column index to node list = std::map [OK]

Hint: Use map to group nodes by column [OK]

Common Mistakes:

• Using vector alone loses column indexing
• Stack or queue do not map keys to values
• Using unordered_map loses column order

3. Given the binary tree:

    1
   / \
  2   3
 /     \
4       5

What is the vertical order traversal output?

medium

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

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

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

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

Solution

1. Step 1: Assign horizontal distances (HD) to nodes

   Root 1 has HD=0; left child 2 has HD=-1; right child 3 has HD=1; 4 is left of 2 so HD=-2; 5 is right of 3 so HD=2.

2. Step 2: Group nodes by HD and list in order

   HD=-2: [4], HD=-1: [2], HD=0: [1], HD=1: [3], HD=2: [5]. Combine left to right: [4, 2, 1, 3, 5].

3. Final Answer:

   [4, 2, 1, 3, 5] -> Option A

4. Quick Check:

   Vertical order = [4, 2, 1, 3, 5] [OK]

Hint: Assign horizontal distances, then list nodes left to right [OK]

Common Mistakes:

• Mixing order of nodes in same vertical column
• Ignoring horizontal distance for children
• Listing nodes by level order instead

4. Consider this code snippet for vertical order traversal:

void verticalOrder(Node* root) {
  map m;
  queue> q;
  q.push({root, 0});
  while (!q.empty()) {
    auto p = q.front(); q.pop();
    Node* node = p.first;
    int hd = p.second;
    m[hd].push_back(node->data);
    if (node->left) q.push({node->left, hd - 1});
    if (node->right) q.push({node->right, hd + 1});
  }
  for (auto &x : m) {
    for (int val : x.second) cout << val << " ";
  }
}

What is the bug in this code?

medium

A. It does not handle empty tree (root == nullptr)

B. It uses map instead of unordered_map causing wrong order

C. It pushes right child before left child in queue

D. It does not store horizontal distances correctly

Solution

1. Step 1: Check for null root before processing

   The code assumes root is not null but does not check. If root is nullptr, q.push({root, 0}) pushes null pointer causing runtime error.

2. Step 2: Verify other parts are correct

   Using map keeps columns sorted, order of pushing left then right is correct, horizontal distances are updated properly.

3. Final Answer:

   It does not handle empty tree (root == nullptr) -> Option A

4. Quick Check:

   Missing null root check causes error [OK]

Hint: Always check if root is nullptr before traversal [OK]

Common Mistakes:

• Ignoring null root causing crash
• Confusing map with unordered_map for order
• Swapping left and right child pushes

5. You want to modify vertical order traversal to print nodes sorted by their depth within each vertical column (top to bottom). Which data structure change helps achieve this?

hard

A. Use map and sort vectors after traversal

B. Use map> to store nodes by column and depth

C. Use unordered_map and sort keys later

D. Use queue> only without map

Solution

1. Step 1: Understand requirement to sort nodes by depth per column

   We need to group nodes by vertical column and also by their depth (level) to print top to bottom.

2. Step 2: Choose data structure to store nodes by column and depth

   Using map> allows mapping column -> depth -> list of nodes, preserving order in both dimensions.

3. Final Answer:

   Use map> to store nodes by column and depth -> Option B

4. Quick Check:

   Nested map for column and depth sorting [OK]

Hint: Use nested map to sort nodes by column and depth [OK]

Common Mistakes:

• Sorting vectors after traversal is inefficient
• Using unordered_map loses order
• Ignoring depth dimension in grouping