Vertical Order Traversal of Binary Tree

Problem Statement

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.

Input/Output Specifications

• Input: The root of a binary tree where 1 <= number of nodes <= 1000 and 0 <= Node.val <= 1000
• Output: A list of lists containing node values in vertical order

Constraints

• 1 <= number of nodes <= 1000
• 0 <= Node.val <= 1000

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9
Column  0: Nodes 3 and 15 (sorted by value)
Column  1: Only node 20
Column  2: Only node 7

Example 2:

Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]

Solution Approaches

Approach 1: DFS with Coordinate Tracking - Optimal

Algorithm Explanation:

1. Use DFS to traverse the tree and assign coordinates to each node
2. Store nodes by their column index in a hash map
3. For each column, sort nodes by row first, then by value
4. Return the result in column order

Implementation:

Python:

from collections import defaultdict

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def verticalTraversal(root):
    """
    Vertical order traversal using DFS with coordinate tracking
    Time: O(n log n)
    Space: O(n)
    """
    if not root:
        return []
    
    # Dictionary to store nodes by column
    column_map = defaultdict(list)
    
    def dfs(node, row, col):
        if not node:
            return
        
        # Store node with its coordinates
        column_map[col].append((row, node.val))
        
        # Traverse left and right children
        dfs(node.left, row + 1, col - 1)
        dfs(node.right, row + 1, col + 1)
    
    # Start DFS from root
    dfs(root, 0, 0)
    
    # Sort columns and build result
    result = []
    for col in sorted(column_map.keys()):
        # Sort nodes in the same column by row, then by value
        column_map[col].sort()
        result.append([val for row, val in column_map[col]])
    
    return result

Java:

import java.util.*;

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

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Map<Integer, List<int[]>> columnMap = new HashMap<>();
        dfs(root, 0, 0, columnMap);
        
        List<Integer> columns = new ArrayList<>(columnMap.keySet());
        Collections.sort(columns);
        
        for (int col : columns) {
            List<int[]> nodes = columnMap.get(col);
            nodes.sort((a, b) -> {
                if (a[0] != b[0]) {
                    return Integer.compare(a[0], b[0]);
                }
                return Integer.compare(a[1], b[1]);
            });
            
            List<Integer> column = new ArrayList<>();
            for (int[] node : nodes) {
                column.add(node[1]);
            }
            result.add(column);
        }
        
        return result;
    }
    
    private void dfs(TreeNode node, int row, int col, Map<Integer, List<int[]>> columnMap) {
        if (node == null) {
            return;
        }
        
        columnMap.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, node.val});
        dfs(node.left, row + 1, col - 1, columnMap);
        dfs(node.right, row + 1, col + 1, columnMap);
    }
}

Complexity Analysis:

• Time Complexity: O(n log n) - DFS traversal + sorting
• Space Complexity: O(n) - Hash map and recursion stack

Key Insights

1. Coordinate System: Assign (row, col) coordinates to each node
2. Column Grouping: Group nodes by their column index
3. Sorting: Sort nodes within each column by row, then by value
4. Traversal Order: DFS or BFS both work for coordinate assignment

Edge Cases

1. Empty Tree: Return empty list
2. Single Node: Return single column with one node
3. Skewed Tree: Handle left-skewed or right-skewed trees
4. Same Column: Multiple nodes in the same column
5. Same Row and Column: Sort by value when coordinates are identical

Test Cases

def test_verticalTraversal():
    # Test case 1
    root1 = TreeNode(3)
    root1.left = TreeNode(9)
    root1.right = TreeNode(20)
    root1.right.left = TreeNode(15)
    root1.right.right = TreeNode(7)
    assert verticalTraversal(root1) == [[9], [3, 15], [20], [7]]
    
    # Test case 2
    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.right = TreeNode(3)
    root2.left.left = TreeNode(4)
    root2.left.right = TreeNode(5)
    root2.right.left = TreeNode(6)
    root2.right.right = TreeNode(7)
    assert verticalTraversal(root2) == [[4], [2], [1, 5, 6], [3], [7]]
    
    print("All tests passed!")

test_verticalTraversal()

Follow-up Questions

1. Horizontal Order: Traverse horizontally by rows?
2. Diagonal Traversal: Traverse diagonally?
3. Boundary Traversal: Traverse only boundary nodes?
4. Spiral Traversal: Traverse in spiral order?
5. Zigzag Traversal: Traverse in zigzag pattern?

Common Mistakes

1. Coordinate Assignment: Incorrect row/column assignment
2. Sorting Logic: Wrong sorting order within columns
3. Column Ordering: Not sorting columns correctly
4. Edge Case Handling: Not handling empty tree or single node
5. Data Structure: Using wrong data structure for column mapping

Interview Tips

1. Start with DFS: Begin with DFS approach
2. Explain Coordinates: Describe the coordinate system
3. Discuss Sorting: Explain sorting requirements
4. Handle Edge Cases: Cover empty tree and special cases
5. Code Carefully: Pay attention to coordinate calculations

Concept Explanations

Vertical Order Traversal: A tree traversal method where nodes are grouped by their column index and returned in column order from left to right.

Coordinate System: A system where each node is assigned (row, col) coordinates based on its position in the tree. The root is at (0, 0), left children move to (row+1, col-1), and right children move to (row+1, col+1).

Column Grouping: The process of grouping nodes by their column index to create vertical columns of nodes.

When to Use: Use this pattern when you need to traverse a tree in a specific spatial order, such as vertical, horizontal, or diagonal traversal.