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

↓

Traverse left subtree

↓

Decrease horizontal distance by 1

↓

Traverse right subtree

↓

Increase horizontal distance by 1

↓

Collect nodes by horizontal distance

↓

Sort nodes by horizontal distance

↓

Output nodes in vertical order

Start from the root with horizontal distance 0, traverse left decreasing distance, right increasing distance, collect nodes by distance, then output sorted vertical lines.

Execution Sample

DSA C

void verticalOrderTraversal(Node* root) {
  // Use queue for BFS with horizontal distance
  // Map horizontal distance to list of nodes
  // Print nodes grouped by horizontal distance
}

This code traverses the binary tree level by level, tracks horizontal distances, groups nodes by these distances, and prints them in vertical order.

Execution Table

Step	Operation	Current Node	Horizontal Distance	Queue State	Map State (HD -> Nodes)	Visual State
1	Start at root	1	0	[(1,0)]	{0: [1]}	1(0) / \ ... ...
2	Dequeue node	1	0	[]	{0: [1]}	1(0)
3	Enqueue left child	2	-1	[(2,-1)]	{0: [1]}	1(0) / \ 2(-1) ...
4	Enqueue right child	3	1	[(2,-1),(3,1)]	{0: [1]}	1(0) / \ 2(-1) 3(1)
5	Dequeue node	2	-1	[(3,1)]	{0: [1], -1: [2]}	1(0) / \ 2(-1) 3(1)
6	Enqueue left child	4	-2	[(3,1),(4,-2)]	{0: [1], -1: [2]}	2(-1) / 4(-2) ...
7	Enqueue right child	5	0	[(3,1),(4,-2),(5,0)]	{0: [1], -1: [2]}	2(-1) / \ 4(-2) 5(0)
8	Dequeue node	3	1	[(4,-2),(5,0)]	{0: [1], -1: [2], 1: [3]}	3(1)
9	Dequeue node	4	-2	[(5,0)]	{0: [1], -1: [2], 1: [3], -2: [4]}	4(-2)
10	Dequeue node	5	0	[]	{0: [1,5], -1: [2], 1: [3], -2: [4]}	5(0)
11	Traversal complete	None	N/A	[]	{-2: [4], -1: [2], 0: [1,5], 1: [3]}	Final vertical order: HD -2: 4 HD -1: 2 HD 0: 1 -> 5 HD 1: 3

💡 Queue empty, all nodes processed

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	Final
Queue	[(1,0)]	[]	[(3,1)]	[(5,0)]	[]
Map (HD -> Nodes)	{}	{0: [1]}	{0: [1], -1: [2]}	{0: [1], -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) to group nodes?

Because nodes with the same HD lie in the same vertical line. The execution_table shows nodes grouped by HD in the Map State column.

Why do we use a queue with nodes and their HDs?

The queue helps traverse the tree level by level while tracking HDs. See the Queue State column in execution_table showing nodes with their HDs.

Why do we add left child with HD-1 and right child with HD+1?

Moving left decreases HD by 1, moving right increases HD by 1. This is shown in the Horizontal Distance column during enqueue operations.

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 the execution_table.

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

A Step 5

B Step 9

C Step 8

D Step 10

💡 Hint

Look at the Map State column in execution_table to see when HD -2 appears.

If the tree had no right child for the root, how would the final map change?

A No nodes at HD 1

B No nodes at HD -1

C No nodes at HD 0

D No nodes at HD -2

💡 Hint

Right child nodes have HD +1, so removing right child removes HD 1 entries.

Concept Snapshot

Vertical Order Traversal:
- Assign horizontal distance (HD) 0 to root
- Left child HD = parent HD - 1
- Right child HD = parent HD + 1
- Use BFS with queue storing (node, HD)
- Group nodes by HD in map
- Output nodes sorted by HD from left to right

Full Transcript

Vertical Order Traversal of a binary tree means printing nodes column by column from left to right. We start at the root with horizontal distance zero. When we go left, we decrease horizontal distance by one; when we go right, we increase it by one. We use a queue to traverse the tree level by level, storing each node with its horizontal distance. We keep a map that groups nodes by their horizontal distance. After traversal, we print nodes grouped by horizontal distance in order from smallest to largest. The execution table shows each step: nodes enqueued with their distances, queue state, and map state. The variable tracker shows how the queue and map change over time. Key moments clarify why horizontal distance is used, why the queue stores nodes with distances, and how left and right children affect distances. The visual quiz tests understanding of queue contents, when distances appear in the map, and effects of missing children.

Practice

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

easy

A. Nodes grouped by their vertical columns from left to right

B. Nodes grouped by their depth levels from top to bottom

C. Nodes visited in preorder traversal order

D. Nodes visited in postorder traversal order

Solution

1. Step 1: Understand vertical order traversal concept

   Vertical order traversal groups nodes by their vertical columns, where the root is at column 0, left child at column -1, right child at column +1, and so on.

2. Step 2: Compare with other traversal types

   Depth levels group nodes horizontally, preorder and postorder are depth-first traversals, not vertical grouping.

3. Final Answer:

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

4. Quick Check:

   Vertical order = vertical columns grouping [OK]

Hint: Vertical order groups nodes by columns, not levels or order [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking preorder or postorder is vertical order
• Mixing horizontal levels with vertical columns

2. Which data structure is commonly used to store nodes during vertical order traversal?

easy

A. Queue

B. HashMap or Dictionary

C. Stack

D. Linked List

Solution

1. Step 1: Identify storage needs for vertical order traversal

   We need to group nodes by their vertical column index, so a map (like HashMap or Dictionary) is used to store lists of nodes per column.

2. Step 2: Understand role of other data structures

   Queue is used for level order traversal but not for grouping columns; stack and linked list do not directly map columns to nodes.

3. Final Answer:

   HashMap or Dictionary -> Option B

4. Quick Check:

   Use map to group nodes by column [OK]

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

Common Mistakes:

• Using stack instead of map for grouping
• Confusing queue usage for traversal with storage
• Not grouping nodes by column properly

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

    1
   / \
  2   3
 / \   \
4   5   6

medium

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

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

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

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

Solution

1. Step 1: Assign vertical columns to each node

   Root 1 is at column 0; 2 is at -1; 3 is at +1; 4 is at -2; 5 is at 0; 6 is at +2.

2. Step 2: Group nodes by columns and read left to right

   Column -2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]. Reading in order: 4, 2, 1, 5, 3, 6.

3. Final Answer:

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

4. Quick Check:

   Group by columns left to right [OK]

Hint: Assign columns: left -1, right +1; group and read left to right [OK]

Common Mistakes:

• Mixing order of nodes in same column
• Ignoring multiple nodes in one column
• Reading nodes top-down instead of column-wise

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

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

medium

A. Not sorting nodes inside each column before printing

B. Using map instead of unordered_map causes slower performance

C. Missing check if root is NULL before pushing to queue

D. Incorrect decrement and increment of column index for children

Solution

1. Step 1: Check initial queue push

   The code pushes root to queue without checking if root is NULL, which can cause runtime error if tree is empty.

2. Step 2: Verify other parts

   Column indices are correctly updated; map usage is valid; sorting nodes inside columns is optional depending on problem.

3. Final Answer:

   Missing check if root is NULL before pushing to queue -> Option C

4. Quick Check:

   Always check root != NULL before queue push [OK]

Hint: Check root != NULL before queue push to avoid errors [OK]

Common Mistakes:

• Ignoring NULL root causing crash
• Thinking map usage is incorrect
• Assuming sorting inside columns is mandatory

5. Given a binary tree, how would you modify vertical order traversal to print nodes sorted by their row (depth) within each vertical column?

hard

A. Store nodes in map>> with (row, value) and sort by row before printing

B. Use a stack instead of queue to traverse nodes depth-first

C. Ignore row and print nodes in order they appear in queue

D. Use unordered_map and sort keys before printing

Solution

1. Step 1: Understand requirement to sort by row within columns

   We need to track both column and row (depth) for each node to sort nodes vertically and then by depth.

2. Step 2: Use map with pairs and sort

   Store nodes in map keyed by column with vector of (row, value) pairs. Sort vector by row before printing to get correct order.

3. Final Answer:

   Store nodes in map<int, vector<pair<int,int>>> with (row, value) and sort by row before printing -> Option A

4. Quick Check:

   Track row and column, sort by row inside columns [OK]

Hint: Track row with column, sort nodes by row inside each column [OK]

Common Mistakes:

• Not tracking row, so nodes unordered by depth
• Using stack breaks level order needed for row tracking
• Ignoring sorting inside columns