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

↓

Dequeue node

↓

Add node value to map at its horizontal distance

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

Repeat until queue empty

↓

Sort map keys

↓

Output nodes grouped by sorted horizontal distances

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#

class Node {
  public int val;
  public Node left, right;
  public Node(int v) { val = v; }
}

// Vertical order traversal using BFS and map

Traverse the binary tree level-wise, track horizontal distances, and group nodes by these distances.

Execution Table

Step	Operation	Node Processed (val)	Horizontal Distance (hd)	Map State (hd: [nodes])	Queue State (val, hd)	Visual Tree State
1	Start at root	1	0	{}	[(1,0)]	1 / \ 2 3
2	Dequeue node	1	0	{0: [1]}	[]	1 / \ 2 3
3	Enqueue left child	2	-1	{0: [1]}	[(2,-1)]	1 / \ 2 3
4	Enqueue right child	3	1	{0: [1]}	[(2,-1), (3,1)]	1 / \ 2 3
5	Dequeue node	2	-1	{0: [1]}	[(3,1)]	1 / \ 2 3
6	Add node to map	2	-1	{-1: [2], 0: [1]}	[(3,1)]	1 / \ 2 3
7	Enqueue left child	4	-2	{-1: [2], 0: [1]}	[(3,1), (4,-2)]	1 / \ 2 3 /
8	Enqueue right child	5	0	{-1: [2], 0: [1]}	[(3,1), (4,-2), (5,0)]	1 / \ 2 3 / \
9	Dequeue node	3	1	{-1: [2], 0: [1]}	[(4,-2), (5,0)]	1 / \ 2 3 / \
10	Add node to map	3	1	{-1: [2], 0: [1], 1: [3]}	[(4,-2), (5,0)]	1 / \ 2 3 / \
11	Dequeue node	4	-2	{-1: [2], 0: [1], 1: [3]}	[(5,0)]	1 / \ 2 3 / \ 4
12	Add node to map	4	-2	{-2: [4], -1: [2], 0: [1], 1: [3]}	[(5,0)]	1 / \ 2 3 / \ 4
13	Dequeue node	5	0	{-2: [4], -1: [2], 0: [1], 1: [3]}	[]	1 / \ 2 3 / \ 4 5
14	Add node to map	5	0	{-2: [4], -1: [2], 0: [1,5], 1: [3]}	[]	1 / \ 2 3 / \ 4 5
15	Queue empty	-	-	{-2: [4], -1: [2], 0: [1,5], 1: [3]}	[]	Traversal complete
16	Sort keys and output	-	-	Output: [[4], [2], [1,5], [3]]	-	-

💡 Queue is empty, all nodes processed, traversal ends.

Variable Tracker

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

Key Moments - 3 Insights

Why do we assign horizontal distance (hd) starting at 0 for root?

The root is the center point, so hd=0 helps measure left nodes as negative and right nodes as positive distances, as shown in execution_table rows 1-4.

Why do we use a queue for traversal instead of recursion?

Queue ensures level order traversal (BFS), so nodes are processed top to bottom and left to right at each horizontal distance, as seen in the queue states in execution_table rows 2-14.

How do we know when to stop traversal?

When the queue is empty, all nodes are processed. This is shown in execution_table row 15 where queue is empty and traversal ends.

Visual Quiz - 3 Questions

Look at the execution_table at step 12, what is the map state?

A {-2: [4], -1: [2], 0: [1], 1: [3]}

B {-2: [4], -1: [2], 0: [1,5], 1: [3]}

C {-2: [4], -1: [2], 0: [1], 1: [3,5]}

D {-1: [2], 0: [1,5], 1: [3]}

💡 Hint

Check execution_table row 12 under 'Map State (hd: [nodes])'

At which step does the queue become empty?

A Step 14

B Step 15

C Step 13

D Step 16

💡 Hint

Look at execution_table row 15 'Queue State' column

If we changed the root's horizontal distance to 1 instead of 0, how would the map keys change?

A All keys increase by 1

B All keys decrease by 1

C Keys remain the same

D Only left child keys change

💡 Hint

Horizontal distance is relative; changing root hd shifts all keys accordingly, see concept_flow

Concept Snapshot

Vertical Order Traversal:
- Assign hd=0 to root
- Use BFS with queue storing (node, hd)
- Map nodes by hd
- Left child hd = hd-1, right child hd = hd+1
- After traversal, output nodes grouped by sorted hd keys

Full Transcript

Vertical order traversal visits nodes by their vertical columns. We start at root with horizontal distance zero. Using a queue, we process nodes level by level, adding their values to a map keyed by horizontal distance. Left children get hd-1, right children hd+1. When queue empties, we output nodes grouped by sorted horizontal distances from left to right.

Practice

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

easy

A. Nodes grouped by their depth level from top to bottom

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

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

D. Nodes visited in postorder (left, right, root)

Solution

1. Step 1: Understand vertical order traversal

   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 traversals

   Unlike level order or preorder, vertical order focuses on columns, not depth or visit order.

3. Final Answer:

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

4. Quick Check:

   Vertical order = nodes by vertical columns [OK]

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

Common Mistakes:

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

2. Which of the following C# code snippets correctly initializes a dictionary to store vertical order traversal results where keys are integers and values are lists of integers?

easy

A. var dict = new Dictionary();

B. var dict = new Dictionary();

C. var dict = new Dictionary();

D. var dict = new List>();

Solution

1. Step 1: Identify the data structure needed

   We need a dictionary with integer keys (vertical columns) and list of integers as values (nodes in that column).

2. Step 2: Match with C# syntax

   var dict = new Dictionary(); correctly declares Dictionary. Others have wrong types or collections.

3. Final Answer:

   var dict = new Dictionary(); -> Option A

4. Quick Check:

   Dictionary for vertical order [OK]

Hint: Use Dictionary for vertical columns and nodes [OK]

Common Mistakes:

• Swapping key and value types
• Using List instead of Dictionary for mapping
• Incorrect generic type order

3. Given the following binary tree and C# code for vertical order traversal, what is the printed output?

    1
   / \
  2   3
 / \   \
4   5   6

// Code snippet:
var result = new Dictionary();
void Traverse(TreeNode node, int col) {
  if (node == null) return;
  if (!result.ContainsKey(col)) result[col] = new List<int>();
  result[col].Add(node.val);
  Traverse(node.left, col - 1);
  Traverse(node.right, col + 1);
}
Traverse(root, 0);
foreach (var col in result.OrderBy(k => k.Key)) {
  Console.Write(string.Join(",", col.Value) + " ");
}

medium

A. 4 2 1 5 3 6

B. 4,2 1,5,3 6

C. 4 2 1,5 3 6

D. 4,2 1 5,3 6

Solution

1. Step 1: Assign columns to nodes

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

2. Step 2: Group nodes by column and order

   col -2: [4], col -1: [2], col 0: [1,5], col 1: [3], col 2: [6]. Printed as 4 2 1,5 3 6 (commas inside multi-node groups, spaces between columns).

3. Final Answer:

   4 2 1,5 3 6 -> Option C

4. Quick Check:

   Vertical groups with commas inside, spaces between [OK]

Hint: Track column indices and group nodes before printing [OK]

Common Mistakes:

• Mixing node order inside columns
• Printing without commas or spaces correctly
• Ignoring column sorting

4. The following C# code attempts vertical order traversal but throws a runtime error. What is the main issue?

void Traverse(TreeNode node, int col, Dictionary dict) {
  if (node == null) return;
  dict[col].Add(node.val);
  Traverse(node.left, col - 1, dict);
  Traverse(node.right, col + 1, dict);
}

var dict = new Dictionary();
Traverse(root, 0, dict);

medium

A. Dictionary should use List<int> as key

B. Traverse method should return a value

C. Incorrect base case for recursion

D. Dictionary keys are not initialized before adding values

Solution

1. Step 1: Analyze dictionary usage

   Code tries to add to dict[col] without checking if key col exists, causing KeyNotFoundException.

2. Step 2: Fix by initializing keys

   Before adding, check if dict contains col; if not, create new List<int> for that key.

3. Final Answer:

   Dictionary keys are not initialized before adding values -> Option D

4. Quick Check:

   Initialize dictionary keys before adding [OK]

Hint: Always check and initialize dictionary keys before adding [OK]

Common Mistakes:

• Assuming dictionary auto-creates keys
• Ignoring null checks on dictionary values
• Confusing recursion base case with dictionary errors

5. You want to perform vertical order traversal but also sort nodes by their depth (top to bottom) within each vertical column. Which data structure and approach is best in C#?

hard

A. Use a Dictionary> and sort each list by depth after traversal

B. Use a Dictionary and enqueue nodes as visited

C. Use a List<int> and sort by node value after traversal

D. Use a Dictionary and push nodes in preorder

Solution

1. Step 1: Understand sorting by depth requirement

   We must store nodes with their depth info to sort them top to bottom within each vertical column.

2. Step 2: Choose data structure and approach

   Dictionary with key as column and value as list of (depth, value) pairs allows sorting by depth after traversal.

3. Final Answer:

   Use a Dictionary> and sort each list by depth after traversal -> Option A

4. Quick Check:

   Store depth with nodes, then sort by depth [OK]

Hint: Store depth with nodes, then sort lists by depth per column [OK]

Common Mistakes:

• Using queue or stack without depth info
• Sorting by node value instead of depth
• Ignoring depth when grouping nodes