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

Concept Flow - Vertical Order Traversal of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for BFS traversal

↓

Dequeue node

↓

Add node value to map at horizontal distance

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

Repeat until queue empty

↓

Collect map entries sorted by horizontal distance

↓

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 Java

class Node {
  int val;
  Node left, right;
}

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

Traverse the binary tree using BFS, track horizontal distances, group nodes by these distances.

Execution Table

Step	Operation	Node Processed	Horizontal Distance (hd)	Map State (hd -> [nodes])	Queue State (node, hd)	Visual Tree State
1	Start at root	1	0	{0: [1]}	[(1,0)]	1 / \ 2 3
2	Dequeue node 1	1	0	{0: [1]}	[]	1 / \ 2 3
3	Enqueue left child 2 with hd -1	2	-1	{0: [1]}	[(2,-1)]	1 / \ 2 3
4	Enqueue right child 3 with hd +1	3	1	{0: [1]}	[(2,-1), (3,1)]	1 / \ 2 3
5	Dequeue node 2	2	-1	{0: [1], -1: [2]}	[(3,1)]	1 / \ 2 3
6	Enqueue left child 4 with hd -2	4	-2	{0: [1], -1: [2]}	[(3,1), (4,-2)]	1 / \ 2 3 /
7	Enqueue right child 5 with hd 0	5	0	{0: [1], -1: [2]}	[(3,1), (4,-2), (5,0)]	1 / \ 2 3 / \
8	Dequeue node 3	3	1	{0: [1], -1: [2], 1: [3]}	[(4,-2), (5,0)]	1 / \ 2 3 / \
9	Enqueue right child 6 with hd 2	6	2	{0: [1], -1: [2], 1: [3]}	[(4,-2), (5,0), (6,2)]	1 / \ 2 3 / \ \ 6
10	Dequeue node 4	4	-2	{0: [1], -1: [2], 1: [3], -2: [4]}	[(5,0), (6,2)]	1 / \ 2 3 / \ \ 4 6
11	Dequeue node 5	5	0	{0: [1,5], -1: [2], 1: [3], -2: [4]}	[(6,2)]	1 / \ 2 3 / \ \ 4 5 6
12	Dequeue node 6	6	2	{0: [1,5], -1: [2], 1: [3], -2: [4], 2: [6]}	[]	1 / \ 2 3 / \ \ 4 5 6
13	Queue empty, traversal done	-	-	{-2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]}	[]	Final vertical order groups

💡 Queue is empty, all nodes processed.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 10	After Step 13 (Final)
Queue	[(1,0)]	[(2,-1), (3,1)]	[(3,1)]	[(5,0), (6,2)]	[]
Map (hd -> nodes)	{}	{0: [1]}	{0: [1], -1: [2]}	{0: [1], -1: [2], -2: [4], 1: [3]}	{-2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]}

Key Moments - 3 Insights

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

The queue stores nodes with their horizontal distances to track their vertical position. This is shown in execution_table rows 3-4 where children are enqueued with hd-1 and hd+1.

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

Because BFS visits nodes level by level, nodes at the same horizontal distance are added to the map in order of their level. See execution_table rows 11 where node 5 is added after node 1 at hd=0.

How do we know when to stop the traversal?

When the queue is empty, meaning all nodes have been processed. This is shown in execution_table row 13.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the horizontal distance of node 4?

A -1

B -2

C 0

D 1

💡 Hint

Check the 'Horizontal Distance (hd)' column at step 6 in execution_table.

At which step does the map first contain nodes at horizontal distance 1?

A Step 8

B Step 10

C Step 4

D Step 12

💡 Hint

Look at the 'Map State' column for hd=1 in execution_table rows.

If node 2 had no right child, how would the queue state change after step 7?

A Queue would have (3,1) only

B Queue would have (3,1), (4,-2), and (5,0)

C Queue would have (3,1) and (4,-2) only

D Queue would be empty

💡 Hint

Check how children are enqueued in execution_table steps 6 and 7.

Concept Snapshot

Vertical Order Traversal of Binary Tree:
- Use BFS with a queue storing (node, horizontal distance)
- Root node hd = 0
- Left child hd = parent hd - 1
- Right child hd = parent hd + 1
- Group nodes by hd in a map
- Output groups sorted by hd from smallest to largest

Full Transcript

Vertical Order Traversal visits nodes level by level, tracking their horizontal distance from the root. We start at the root with hd=0, then enqueue left and right children with hd-1 and hd+1 respectively. Using a queue, we process nodes in BFS order, adding their values to a map keyed by hd. After processing all nodes, we output the nodes grouped by their horizontal distances from leftmost to rightmost. This method ensures nodes are grouped vertically and ordered top to bottom within each vertical line.

Practice

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

easy

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

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

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

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

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

   Nodes in the same vertical column are collected and output from leftmost to rightmost column.

3. Final Answer:

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

4. Quick Check:

   Vertical order = group by columns [OK]

Hint: Think columns from left to right, not rows or preorder [OK]

Common Mistakes:

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

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

easy

A. ArrayList<Integer>

B. HashMap

C. Stack<Integer>

D. Queue<Integer>

Solution

1. Step 1: Identify need to map columns to nodes

   We need to group nodes by their vertical column index, so a map from column to list of nodes is needed.

2. Step 2: Choose suitable Java data structure

   A HashMap with key as column index (Integer) and value as list of nodes (List<Integer>) fits perfectly.

3. Final Answer:

   HashMap -> Option B

4. Quick Check:

   Map column to nodes = HashMap [OK]

Hint: Use map from column index to list of nodes [OK]

Common Mistakes:

• Using ArrayList alone without mapping columns
• Using Stack or Queue which don't map keys to lists
• Confusing data structures for traversal order

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

    1
   / \
  2   3
 / \   \
4   5   6

medium

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

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

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

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

Solution

1. Step 1: Assign column indices to nodes

   Root 1 is at column 0. Left child 2 at -1, right child 3 at +1. 4 at -2, 5 at 0, 6 at +2.

2. Step 2: Collect nodes column-wise from left to right

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

3. Final Answer:

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

4. Quick Check:

   Columns left to right = [4,2,1,5,3,6] [OK]

Hint: Label columns from root 0, left -1, right +1, then read left to right [OK]

Common Mistakes:

• Ignoring multiple nodes in same column order
• Mixing preorder or inorder output with vertical order
• Not assigning correct column indices

4. Given this Java snippet for vertical order traversal, what is the error?

Map map = new HashMap<>();
Queue> queue = new LinkedList<>();
queue.add(new Pair(root, 0));
while (!queue.isEmpty()) {
  Pair p = queue.poll();
  TreeNode node = p.getKey();
  int col = p.getValue();
  map.putIfAbsent(col, new ArrayList<>());
  map.get(col).add(node.val);
  if (node.left != null) queue.add(new Pair(node.left, col - 1));
  if (node.right != null) queue.add(new Pair(node.right, col + 1));
}

medium

A. Pair class is not imported or defined

B. Queue should be a Stack for correct traversal

C. map.putIfAbsent should be replaced with map.put

D. col should be incremented for left child, not decremented

Solution

1. Step 1: Check usage of Pair class

   The code uses Pair but Java does not have Pair by default; it must be imported or defined.

2. Step 2: Identify missing import or definition

   Without importing javafx.util.Pair or defining a custom Pair class, this code will not compile.

3. Final Answer:

   Pair class is not imported or defined -> Option A

4. Quick Check:

   Missing Pair class causes compile error [OK]

Hint: Check if all classes like Pair are imported or defined [OK]

Common Mistakes:

• Assuming Pair is built-in in Java standard library
• Using Stack instead of Queue for BFS traversal
• Incorrect column increment direction for left child

5. How would you modify vertical order traversal to output nodes sorted by row and then value within each vertical column? Choose the best approach.

hard

A. Use a Queue and print nodes as they are visited

B. Use a HashMap and sort each list after traversal

C. Use a Stack to store nodes and pop in sorted order

D. Use a TreeMap> to map column -> row -> sorted nodes

Solution

1. Step 1: Understand sorting by row and value in vertical columns

   We need to group nodes by column, then by row, and sort nodes with same row by value.

2. Step 2: Choose data structure supporting nested sorting

   TreeMap for columns and rows keeps keys sorted. PriorityQueue stores nodes sorted by value. So TreeMap> fits.

3. Final Answer:

   Use a TreeMap> to map column -> row -> sorted nodes -> Option D

4. Quick Check:

   Nested TreeMaps + PriorityQueue = sorted vertical order [OK]

Hint: Use nested TreeMaps and PriorityQueue for sorted vertical order [OK]

Common Mistakes:

• Sorting lists after traversal loses row info
• Using Stack or Queue which don't sort nodes
• Ignoring row sorting within columns