Vertical Order Traversal of Binary Tree in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Vertical Order Traversal for a Simple Tree

What is the output of the vertical order traversal for the given binary tree?

DSA C#

class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int x) { val = x; }
}

// Tree structure:
//      1
//     / \
//    2   3
//   /     \
//  4       5

// Vertical order traversal groups nodes by their vertical columns.

// Expected output format: [[4], [2], [1], [3], [5]]

// Code to perform vertical order traversal is assumed correct and omitted for brevity.

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

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

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

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

💡 Hint

Think about how nodes align vertically from left to right.

Vertical order traversal groups nodes by their horizontal distance from the root. Nodes to the left have negative distance, root is zero, right is positive.

Here, 4 is farthest left, then 2, then 1, then 3, then 5.

🧠 Conceptual

intermediate

Understanding Horizontal Distance in Vertical Order Traversal

In vertical order traversal, what does the 'horizontal distance' of a node represent?

A The distance of the node from the root measured horizontally, with root at 0, left child -1, right child +1

B The depth level of the node in the tree

C The number of nodes in the subtree rooted at that node

D The vertical height of the node from the bottom of the tree

💡 Hint

It helps group nodes vertically by their horizontal position.

Horizontal distance is how far left or right a node is from the root horizontally.

Root is 0, left child decreases by 1, right child increases by 1.

❓ Predict Output

advanced

Output of Vertical Order Traversal with Multiple Nodes in Same Column

What is the output of vertical order traversal for the following tree? // Tree: // 1 // / \ // 2 3 // \ \ // 4 5 // / \ // 6 7 // Expected output format: list of lists of node values by vertical columns.

DSA C#

class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int x) { val = x; }
}

// Vertical order traversal groups nodes by horizontal distance.
// Nodes in the same column are listed top to bottom.

// Code to perform traversal is assumed correct and omitted.

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

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

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

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

💡 Hint

Remember nodes in the same vertical column are ordered top to bottom.

Nodes with horizontal distance -1: 2, then 6 (top to bottom)

Distance 0: 1, then 4 (top to bottom)

Distance 1: 3

Distance 2: 5

Distance 3: 7

🔧 Debug

advanced

Identify the Error in Vertical Order Traversal Code

Given the following code snippet for vertical order traversal, what error will it cause when run? class TreeNode { public int val; public TreeNode left, right; public TreeNode(int x) { val = x; } } void VerticalOrder(TreeNode root) { var map = new Dictionary>(); Queue<(TreeNode node, int hd)> queue = new Queue<(TreeNode, int)>(); queue.Enqueue((root, 0)); while(queue.Count > 0) { var (node, hd) = queue.Dequeue(); map[hd].Add(node.val); if(node.left != null) queue.Enqueue((node.left, hd - 1)); if(node.right != null) queue.Enqueue((node.right, hd + 1)); } }

A NullReferenceException because node can be null in queue

B No error, code runs correctly

C KeyNotFoundException because map[hd] is accessed before initialization

D SyntaxError due to tuple deconstruction in queue.Dequeue()

💡 Hint

Check if the dictionary key exists before adding to the list.

The dictionary 'map' does not initialize a list for a new horizontal distance key before adding values.

Accessing map[hd] when hd is not a key causes KeyNotFoundException.

🚀 Application

expert

Number of Vertical Columns in a Complex Tree

Given the binary tree below, how many vertical columns will the vertical order traversal produce? // Tree: // 10 // / \ // 7 15 // / \ // 5 8 20 // / \ // 3 25 // Count the distinct horizontal distances from the root.

A 7

B 5

C 6

D 4

💡 Hint

Calculate horizontal distances for each node and count unique values.

Horizontal distances:

• 10: 0
• 7: -1
• 15: 1
• 5: -2
• 8: 0
• 20: 2
• 3: -3
• 25: 3

Unique distances: -3, -2, -1, 0, 1, 2, 3 → 7 columns

But 8 shares 0 with 10, so total unique columns are 7.

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