Vertical Order Traversal of Binary Tree in DSA C#

Mental Model

We want to print tree nodes column by column from left to right, grouping nodes that share the same vertical line.

Analogy: Imagine standing in front of a tree and looking straight at it. Nodes that line up vertically in your view belong to the same column. We collect nodes column-wise from left to right.

      1
     / \
    2   3
   / \   \
  4   5   6

Columns:  -2  -1   0   1   2
Nodes:    4   2   1,5   3   6

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6

Goal: Print nodes grouped by vertical columns from left to right

Step 1: Start at root node 1 with column 0

Column 0: [1]

Why: Root is the center column, so we assign it column 0

Step 2: Move to left child 2 with column -1

Column -1: [2]
Column 0: [1]

Why: Left child is one column to the left

Step 3: Move to left child 4 with column -2

Column -2: [4]
Column -1: [2]
Column 0: [1]

Why: Left child again moves one column left

Step 4: Back to 2, move to right child 5 with column 0

Column -2: [4]
Column -1: [2]
Column 0: [1,5]

Why: Right child moves one column right from parent

Step 5: Back to root 1, move to right child 3 with column 1

Column -2: [4]
Column -1: [2]
Column 0: [1,5]
Column 1: [3]

Why: Right child moves one column right

Step 6: Move to right child 6 of 3 with column 2

Column -2: [4]
Column -1: [2]
Column 0: [1,5]
Column 1: [3]
Column 2: [6]

Why: Right child moves one column right again

Result:

4 -> 2 -> 1,5 -> 3 -> 6

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public IList<IList<int>> VerticalOrder(TreeNode root) {
        var result = new List<IList<int>>();
        if (root == null) return result;

        // Dictionary to hold column index and list of nodes
        var columnTable = new SortedDictionary<int, List<int>>();

        // Queue for BFS: stores node and its column index
        var queue = new Queue<(TreeNode node, int col)>();
        queue.Enqueue((root, 0));

        while (queue.Count > 0) {
            var (node, col) = queue.Dequeue();

            if (!columnTable.ContainsKey(col)) {
                columnTable[col] = new List<int>();
            }
            columnTable[col].Add(node.val); // add node to its column list

            if (node.left != null) queue.Enqueue((node.left, col - 1)); // left child column -1
            if (node.right != null) queue.Enqueue((node.right, col + 1)); // right child column +1
        }

        // Collect results from leftmost to rightmost column
        foreach (var key in columnTable.Keys) {
            result.Add(columnTable[key]);
        }

        return result;
    }

    public static void Main() {
        // Build tree: 1
        //          /   \
        //         2     3
        //        / \     \
        //       4   5     6
        var root = new TreeNode(1,
                    new TreeNode(2,
                        new TreeNode(4),
                        new TreeNode(5)),
                    new TreeNode(3,
                        null,
                        new TreeNode(6)));

        var sol = new Solution();
        var verticalOrder = sol.VerticalOrder(root);

        foreach (var col in verticalOrder) {
            Console.WriteLine(string.Join(",", col));
        }
    }
}

queue.Enqueue((root, 0));

Start BFS with root at column 0

var (node, col) = queue.Dequeue();

Process next node and its column

if (!columnTable.ContainsKey(col)) { columnTable[col] = new List<int>(); }

Create list for column if not exists

columnTable[col].Add(node.val);

Add current node value to its column list

if (node.left != null) queue.Enqueue((node.left, col - 1));

Add left child with column one less

if (node.right != null) queue.Enqueue((node.right, col + 1));

Add right child with column one more

foreach (var key in columnTable.Keys) { result.Add(columnTable[key]); }

Collect columns from left to right

Output

4

2

1,5

3

6

Complexity Analysis

Time: O(n) because we visit each node once during BFS

Space: O(n) for storing nodes in the dictionary and queue

vs Alternative: Compared to DFS, BFS ensures nodes are added in top-to-bottom order per column, which matches vertical order traversal requirements

Edge Cases

Empty tree (root is null)

Returns empty list without error

DSA C#

if (root == null) return result;

Tree with only one node

Returns list with single column containing that node

DSA C#

queue.Enqueue((root, 0));

Tree with multiple nodes in same column

Nodes appear in order from top to bottom in that column list

DSA C#

columnTable[col].Add(node.val);

When to Use This Pattern

When a problem asks to print or group tree nodes by vertical columns, use vertical order traversal with BFS and column indexing to maintain correct order.

Common Mistakes

Mistake: Using DFS instead of BFS causing nodes in same column to be out of top-to-bottom order
Fix: Use BFS traversal with a queue to process nodes level by level

Mistake: Not tracking column indices correctly, mixing left and right child columns
Fix: Assign left child column as parent column minus one, right child as parent column plus one

Summary

Groups binary tree nodes by their vertical columns from left to right.

Use when you need to print or analyze tree nodes column-wise.

Track column indices during BFS to collect nodes in correct vertical order.

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