Vertical Order Traversal of a Binary Tree

This chapter explores how to perform a Vertical Order Traversal on a given binary tree. Unlike standard level-order or depth-first traversals (pre-order, in-order, post-order) that visit nodes level by level or branch by branch, vertical order traversal requires us to slice the tree vertically from left to right—projecting every node onto vertical columns along an imaginary X-axis—and then sorting nodes by their depth (level) and value when collisions occur.

1. Why Do We Need This? (The Problem Statement)

Standard tree traversals (such as Breadth-First Search or Depth-First Search) organize nodes by depth or ancestral relationships. However, geometric and spatial problems often require grouping nodes based on their horizontal alignment (vertical columns).

• The Goal: Return a list of lists (or vector of vectors) where each inner list contains all nodes falling on a specific vertical line, ordered from left to right, and for any specific vertical line, ordered from top to bottom (level by level).
• The Overlap Challenge: If two or more nodes share the exact same vertical coordinate ($X$) and the exact same level ($Y$), we must output them in ascending order of their node values.

2. Core Mental Model: The X-Axis and Level Coordinate System

To map a 2D tree structure into vertical columns, the creator introduces a coordinate system based on two parameters for every node:

1. Vertical Index ($X$-coordinate): Represents the horizontal column.
   • Moving to the left child decreases the $X$ coordinate by 1 ($X - 1$).
   • Moving to the right child increases the $X$ coordinate by 1 ($X + 1$).
2. Level Index ($Y$-coordinate): Represents the depth or vertical distance from the root.
   • Moving down to any child (left or right) increases the level by 1 ($Y + 1$).

Real-Life Analogy: The Grid Projection

Analogy: Imagine shining a bright overhead light straight down onto a binary tree resting on a coordinate grid. Each node casts a shadow onto the $X$-axis. Nodes that land on the exact same $X$-coordinate belong to the same vertical "slice." Within that slice, nodes higher up are closer to the top, while nodes sharing both the same vertical slice and the same height are ordered numerically.

                  [1] (X=0, Level=0)
                 /   \
  (X=-1, L=1) [2]     [3] (X=1, Level=1)
             /   \   /   \
(X=-2, L=2) [4]  [10] [9]  [10] (X=2, Level=2)

3. Naive vs. Better Approach

The Naive Approach

• Attempting to collect nodes purely through recursive DFS without tracking coordinates makes it difficult to group them into sorted columns.
• Storing nodes without a self-balancing data structure requires manual sorting passes over every column and level, leading to inefficient $O(N \log N \text{ per level})$ overheads and complex boundary checks.

The Optimal Approach (Queue + Nested Maps with Multi-sets/Priority Queues)

• Queue for Traversal: Perform a level-order traversal (BFS) using a queue to process nodes systematically while dynamically calculating their $(X, Y)$ coordinates.
• Nested Ordered Maps: Store the mapped nodes in an ordered map where the outer key represents the vertical column ($X$), and the inner key represents the level ($Y$).
• Multiset / Priority Queue: Because multiple nodes can share the exact same vertical column and level, use a Multiset (C++) or Priority Queue / Tree Map (Java) to automatically keep nodes sorted by their values.

4. Step-by-Step Traversal Flow

Let's trace how coordinates evolve as we traverse down the tree:

1. Root Initialization: Start at the root node 1 with coordinates X = 0, Level = 0. Push (node: 1, vertical: 0, level: 0) into the BFS queue.
2. Processing Left Child: When moving from parent (X, Level) to its left child:
   • New Vertical ($X$) = X - 1
   • New Level = Level + 1
3. Processing Right Child: When moving from parent (X, Level) to its right child:
   • New Vertical ($X$) = X + 1
   • New Level = Level + 1

Flow Walkthrough Diagram

5. Data Structure Architecture

To implement this efficiently across languages, we utilize nested maps paired with ordered collections:

6. Complete Implementation Code

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        // Map structure: map[vertical][level] = multiset of node values
        map<int, map<int, multiset<int>>> nodes;
        
        // Queue stores: {node, {vertical, level}}
        queue<pair<TreeNode*, pair<int, int>>> todo;
        
        if (root != NULL) {
            todo.push({root, {0, 0}});
        }
        
        while (!todo.empty()) {
            auto p = todo.front();
            todo.pop();
            
            TreeNode* node = p.first;
            int x = p.second.first;
            int y = p.second.second;
            
            // Insert node value into corresponding vertical and level
            nodes[x][y].insert(node->val);
            
            // Push left child with updated coordinates (x - 1, y + 1)
            if (node->left != NULL) {
                todo.push({node->left, {x - 1, y + 1}});
            }
            
            // Push right child with updated coordinates (x + 1, y + 1)
            if (node->right != NULL) {
                todo.push({node->right, {x + 1, y + 1}});
            }
        }
        
        vector<vector<int>> ans;
        for (auto p : nodes) {
            vector<int> col;
            for (auto q : p.second) {
                // Insert all elements from the multiset into the column vector
                col.insert(col.end(), q.second.begin(), q.second.end());
            }
            ans.push_back(col);
        }
        return ans;
    }
};

Java Implementation

import java.util.*;

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

class Tuple {
    TreeNode node;
    int vertical;
    int level;
    Tuple(TreeNode _node, int _vertical, int _level) {
        node = _node;
        vertical = _vertical;
        level = _level;
    }
}

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        // TreeMap to store vertical -> (level -> PriorityQueue)
        TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new TreeMap<>();
        Queue<Tuple> queue = new LinkedList<>();
        
        if (root != null) {
            queue.offer(new Tuple(root, 0, 0));
        }
        
        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            TreeNode node = tuple.node;
            int x = tuple.vertical;
            int y = tuple.level;
            
            // Initialize maps and priority queue if they do not exist
            if (!map.containsKey(x)) {
                map.put(x, new TreeMap<>());
            }
            if (!map.get(x).containsKey(y)) {
                map.get(x).put(y, new PriorityQueue<>());
            }
            map.get(x).get(y).offer(node.val);
            
            // Traverse left child
            if (node.left != null) {
                queue.offer(new Tuple(node.left, x - 1, y + 1));
            }
            
            // Traverse right child
            if (node.right != null) {
                queue.offer(new Tuple(node.right, x + 1, y + 1));
            }
        }
        
        List<List<Integer>> list = new ArrayList<>();
        for (int vertical : map.keySet()) {
            List<Integer> col = new ArrayList<>();
            for (int level : map.get(vertical).keySet()) {
                PriorityQueue<Integer> pq = map.get(vertical).get(level);
                while (!pq.isEmpty()) {
                    col.add(pq.poll());
                }
            }
            list.add(col);
        }
        return list;
    }
}

7. Complexity Analysis

• Time Complexity: $\mathcal{O}(N \log N)$
  • Traversing all nodes takes $\mathcal{O}(N)$ time.
  • Inserting each node into a self-balancing ordered map and a multiset (or PriorityQueue) introduces a logarithmic factor ($\log N$) per insertion.
• Space Complexity: $\mathcal{O}(N)$
  • The queue holds at most $\mathcal{O}(N)$ nodes during the BFS traversal.
  • The nested map data structures store all $N$ tree nodes across their respective coordinates, maintaining linear space complexity.

8. Summary and Key Takeaways

• Geometric Coordinate Mapping: Vertical order traversal requires mapping tree nodes to a 2D plane using a horizontal axis ($X$) and a depth level axis ($Y$).
• Coordinate Transformation Rules: Moving left modifies coordinates to (X - 1, Level + 1), while moving right modifies coordinates to (X + 1, Level + 1).
• Handling Collisions: When multiple nodes share the same vertical column and level, use sorted containers like multiset (C++) or PriorityQueue (Java) to guarantee ascending value order.
• Level-Order BFS Foundation: Breadth-First Search using a queue guarantees that nodes are visited level-by-level, preserving relative depth order.
• Ordered Maps for Output: Utilizing std::map (C++) or TreeMap (Java) automatically sorts the vertical columns from leftmost ($-\infty$) to rightmost ($+\infty$).