Vertical Order Traversal of Binary Tree in DSA C# - Deep Dive

Overview - Vertical Order Traversal of Binary Tree

What is it?

Vertical Order Traversal of a Binary Tree is a way to visit all nodes of the tree column by column, from left to right. Each column groups nodes that share the same horizontal distance from the root. We list nodes top to bottom within each column. This helps us see the tree from a vertical perspective instead of the usual horizontal level order.

Why it matters

Without vertical order traversal, we only see trees in horizontal layers or simple left-right orders. Vertical traversal reveals hidden structures and relationships between nodes that share the same vertical line. This is useful in graphics, printing trees, and solving problems where vertical alignment matters. Without it, some tree patterns and queries would be harder to understand or solve.

Where it fits

Before learning vertical order traversal, you should understand binary trees and level order traversal. After mastering this, you can explore more complex tree traversals like diagonal or boundary traversal, and advanced tree problems involving coordinates or spatial queries.

Mental Model

Core Idea

Vertical order traversal groups tree nodes by their horizontal distance from the root and lists them top to bottom within each group.

Think of it like...

Imagine standing in front of a tall bookshelf with many shelves (levels) and columns. Vertical order traversal is like reading the books column by column from left to right, top shelf to bottom shelf, instead of row by row.

          (root)
             1
           /   \
          2     3
         / \   / \
        4   5 6   7

Horizontal distances:
Node 1: 0
Node 2: -1
Node 3: +1
Node 4: -2
Node 5: 0
Node 6: 0
Node 7: +2

Vertical order groups:
-2: 4
-1: 2
 0: 1 -> 5 -> 6
+1: 3
+2: 7

Build-Up - 6 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. The top node is called the root. Each child can have its own children, forming a branching structure. We can represent it with nodes linked by pointers.

Result

You can visualize and represent any binary tree with nodes and their left/right links.

Understanding the basic tree structure is essential because vertical order traversal depends on knowing each node's position relative to the root.

2

Foundation

Horizontal Distance Concept

Concept: Introduce the idea of horizontal distance (HD) from the root to each node.

Assign the root node a horizontal distance (HD) of 0. For any node, its left child has HD = parent's HD - 1, and its right child has HD = parent's HD + 1. This number tells us the vertical column where the node belongs.

Result

Every node in the tree has a unique HD value that groups it into a vertical column.

Knowing HD lets us group nodes vertically, which is the core of vertical order traversal.

3

Intermediate

Level Order Traversal with HD Tracking

🤔Before reading on: do you think we can find vertical order by just sorting nodes by HD? Commit to yes or no.

Concept: Combine level order traversal with tracking each node's HD to visit nodes top to bottom and group by HD.

Use a queue to do level order traversal. Along with each node, store its HD. When you pop a node, add its value to a map keyed by HD. Enqueue its children with updated HDs. This ensures nodes are processed top to bottom within each vertical column.

Result

You get a map from HD to a list of nodes in top-to-bottom order for that vertical column.

Combining level order with HD tracking ensures vertical columns are ordered vertically, not just grouped.

4

Intermediate

Sorting and Output Formatting

🤔Before reading on: do you think the HD keys in the map are always in order? Commit to yes or no.

Concept: After traversal, sort the HD keys from smallest to largest to output columns left to right.

The map keys (HDs) may not be in order because we add nodes as we visit them. Sort the keys to print vertical columns from leftmost to rightmost. Then print the node lists for each HD in order.

Result

The final output is a list of vertical columns, each showing nodes top to bottom, left to right.

Sorting HD keys is necessary to present vertical order traversal in the correct left-to-right sequence.

5

Advanced

Handling Nodes at Same Position

🤔Before reading on: if two nodes share the same HD and level, do you think order matters? Commit to yes or no.

Concept: When nodes share the same HD and level, order them by their value to maintain consistency.

Use a data structure that stores nodes by HD and level. For nodes with same HD and level, sort by node value. This avoids ambiguity in output order and matches problem requirements.

Result

Vertical order traversal output is stable and deterministic even when nodes overlap vertically and horizontally.

Ordering nodes by value when positions tie prevents unpredictable outputs and aligns with common problem constraints.

6

Expert

Optimizing with Balanced Trees and Maps

🤔Before reading on: do you think using a balanced tree map improves performance over a hash map here? Commit to yes or no.

Concept: Use balanced tree maps (like SortedDictionary in C#) to keep HD keys sorted automatically, reducing sorting overhead.

Instead of a hash map, use a balanced tree map keyed by HD. Insert nodes during traversal. This keeps keys sorted, so no extra sorting step is needed. Also, use nested balanced maps for levels to maintain order.

Result

Vertical order traversal runs efficiently with automatic ordering, suitable for large trees.

Choosing the right data structures can optimize vertical order traversal by maintaining order during insertion, not after.

Under the Hood

Vertical order traversal works by assigning each node a horizontal distance (HD) from the root and a level (depth). A breadth-first search (level order) visits nodes top to bottom. Nodes are grouped by HD in a map. When nodes share HD and level, they are sorted by value. The traversal uses a queue to process nodes and a map of maps (HD -> level -> nodes) to store nodes. After traversal, the map is read in order of HD and level to produce the final vertical order.

Why designed this way?

This method was designed to capture both vertical and horizontal positioning of nodes. Using HD and level together solves ambiguity when nodes overlap vertically. Level order traversal ensures top-to-bottom order. Balanced maps or sorting ensure left-to-right column order. Alternatives like simple DFS fail to guarantee correct vertical and top-to-bottom order.

┌───────────────┐
│   Start root  │
│ HD=0, level=0 │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Enqueue root  │
│ with HD=0     │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ While queue not empty:       │
│  Dequeue node, HD, level    │
│  Add node to map[HD][level] │
│  Enqueue left child with    │
│  HD-1, level+1 if exists    │
│  Enqueue right child with   │
│  HD+1, level+1 if exists    │
└─────────────┬───────────────┘
              │
              ▼
┌─────────────────────────────┐
│ After traversal:             │
│ For each HD in sorted order: │
│   For each level in sorted:  │
│     Output nodes sorted by  │
│     value if tie            │
└─────────────────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does vertical order traversal always match level order traversal? Commit to yes or no.

Common Belief: Vertical order traversal is just level order traversal with a different name.

Reality: Vertical order traversal groups nodes by horizontal distance, not just by level. Nodes at the same level can appear in different vertical columns.

Why it matters: Confusing these leads to wrong outputs and misunderstanding of tree structure, especially in problems requiring vertical grouping.

Quick: If two nodes share the same HD, are they always printed in the order they appear in traversal? Commit to yes or no.

Common Belief: Nodes with the same horizontal distance are printed in the order they are visited.

Reality: Nodes with the same HD and level must be sorted by value to maintain consistent order.

Why it matters: Ignoring this causes inconsistent or incorrect outputs, especially in tests requiring stable ordering.

Quick: Can DFS alone produce correct vertical order traversal? Commit to yes or no.

Common Belief: Depth-first search (DFS) is enough to get vertical order traversal.

Reality: DFS does not guarantee top-to-bottom order within vertical columns; level order traversal is needed.

Why it matters: Using DFS alone can produce nodes out of vertical order, breaking problem requirements.

Quick: Is sorting the HD keys after traversal optional? Commit to yes or no.

Common Belief: The order of horizontal distances in the map does not affect the output.

Reality: Sorting HD keys is essential to print vertical columns from left to right correctly.

Why it matters: Skipping sorting leads to jumbled vertical columns and wrong final output.

Expert Zone

1

Using a nested balanced map keyed by HD and level allows automatic ordering without explicit sorting after traversal.

2

When nodes share HD and level, sorting by node value is often required by problem statements but is not inherent to the traversal itself.

3

Memory usage can be optimized by streaming output during traversal if the tree is very large and balanced maps are used.

When NOT to use

Vertical order traversal is not suitable when only horizontal or level order information is needed. For example, if you only want nodes level by level, use level order traversal. For diagonal or boundary views, specialized traversals are better. Also, for very large trees where memory is limited, streaming or partial traversals may be preferred.

Production Patterns

In production, vertical order traversal is used in graphical tree visualizations, printing trees in columnar formats, and spatial queries in databases. It is often combined with coordinate compression or augmented with additional data to handle weighted or labeled trees. Efficient implementations use balanced trees or priority queues to maintain order during traversal.

Connections

Level Order Traversal

Vertical order traversal builds on level order traversal by adding horizontal distance tracking.

Understanding level order traversal is key because vertical order traversal uses it to ensure top-to-bottom ordering within columns.

Coordinate Geometry

Vertical order traversal assigns coordinates (HD, level) to nodes, similar to points on a plane.

Seeing nodes as points with coordinates helps understand grouping and sorting, linking tree traversal to spatial reasoning.

Printing Text Columns

Vertical order traversal is like printing text in columns, where each column groups related content vertically.

This connection shows how data structures relate to formatting and layout problems in user interfaces and printing.

Common Pitfalls

#1 Ignoring horizontal distance and just doing level order traversal.

Wrong approach:

Queue q = new Queue();
q.Enqueue(root);
while(q.Count > 0) {
var node = q.Dequeue();
Console.Write(node.val + " ");
if(node.left != null) q.Enqueue(node.left);
if(node.right != null) q.Enqueue(node.right);
}

Correct approach:

Queue<(Node node, int hd)> q = new Queue<(Node, int)>();
q.Enqueue((root, 0));
var map = new SortedDictionary>();
while(q.Count > 0) {
var (node, hd) = q.Dequeue();
if(!map.ContainsKey(hd)) map[hd] = new List();
map[hd].Add(node.val);
if(node.left != null) q.Enqueue((node.left, hd - 1));
if(node.right != null) q.Enqueue((node.right, hd + 1));
}
foreach(var key in map.Keys) {
Console.WriteLine(string.Join(" ", map[key]));
}

Root cause:

Not tracking horizontal distance means nodes cannot be grouped vertically, so output is just level order.

#2 Not sorting the horizontal distance keys before output.

Wrong approach:

foreach(var key in map.Keys) {
Console.WriteLine(string.Join(" ", map[key]));
} // map.Keys is unordered if using Dictionary

Correct approach:

foreach(var key in map.Keys.OrderBy(k => k)) {
Console.WriteLine(string.Join(" ", map[key]));
}

Root cause:

Using an unordered dictionary without sorting keys leads to columns printed in random order.

#3 Using DFS without level tracking to get vertical order.

Wrong approach:

void DFS(Node node, int hd) {
if(node == null) return;
map[hd].Add(node.val);
DFS(node.left, hd - 1);
DFS(node.right, hd + 1);
}
DFS(root, 0);

Correct approach:

Use BFS with queue storing (node, hd, level) to ensure top-to-bottom order and handle ties.

Root cause:

DFS does not guarantee nodes are visited top to bottom, so vertical order is incorrect.

Key Takeaways

Vertical order traversal groups nodes by their horizontal distance from the root and lists them top to bottom within each group.

Tracking horizontal distance and level during a breadth-first traversal is essential to produce correct vertical order.

Sorting horizontal distance keys after traversal ensures columns are output from left to right.

When nodes share the same position, sorting by node value maintains consistent and stable output.

Choosing the right data structures like balanced maps can optimize traversal and output ordering.

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