Vertical Order Traversal of a Binary Tree

LeetCode 1029 | Difficulty: Hard

Hard

Problem Description

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Return the vertical order traversal of the binary tree.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.

Example 2:

Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
          1 is at the top, so it comes first.
          5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.

Example 3:

Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.

Constraints:

- The number of nodes in the tree is in the range `[1, 1000]`.

- `0 <= Node.val <= 1000`

Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search, Sorting, Binary Tree

---

Approach

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

Tree BFS (Level-Order)

Use a queue to process the tree level by level. At each level, process all nodes in the queue, then add their children. Track the level size to know when one level ends and the next begins.

When to use

Level-order traversal, level-based aggregation, right/left side view.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 188 ms)

Metric	Value
Runtime	188 ms
Memory	41.5 MB
Date	2022-02-23

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode 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>> VerticalTraversal(TreeNode root) {
       IList<IList<int>> result = new List<IList<int>>();
    if(root == null) return result;
    Queue<(TreeNode, int)> q = new Queue<(TreeNode, int)>();
    Dictionary<int, List<int[]>> map = new Dictionary<int, List<int[]>>();
    q.Enqueue((root, 0));
    int min=0, max = 0;
    int row = 0;
    while(q.Count != 0)
    {
        int levelSize = q.Count;
        for (int j = 0; j < levelSize; j++)
        {
            var front = q.Dequeue();
            var node = front.Item1;
            var col = front.Item2;
            if (map.ContainsKey(col)) map[col].Add(new int[] { row, col, node.val });
            else map.Add(col, new List<int[]>() { new int[] { row, col, node.val } });
            if (node.left != null)
            {
                min = Math.Min(min, col - 1);
                q.Enqueue((node.left, col - 1));
            }
            if (node.right != null)
            {
                max = Math.Max(max, col + 1);
                q.Enqueue((node.right, col + 1));
            }
        }
        row++;
    }
    for (int i = min; i <= max; i++)
    {
        if(!map.ContainsKey(i)) continue;
        map[i].Sort(new VerticalComparer());
        result.Add(map[i].Select(x=>x[2]).ToList());
    }
    return result;
}

public class VerticalComparer : IComparer<int[]>
{
    public int Compare(int[] x, int[] y)
    {
        if(x[0]==y[0]) return x[2].CompareTo(y[2]);
        else
        return x[0].CompareTo(y[0]);
    }
}
}

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• Hash map gives O(1) lookup — think about what to use as key vs value.