Vertical Order Traversal

Problem Statement

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

Rules:

• Nodes are grouped by their column (Horizontal Distance).
• If multiple nodes share the same row and column, sort them by value.

Brute Force Intuition

In an interview, you can explain it like this:

Traverse every node, store its row and column information, then sort all collected nodes based on column, row, and value.

Although correct, sorting all nodes together becomes expensive.

Complexity

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Moving Towards the Optimal Approach

Observe that every node has:

Column (Horizontal Distance)

+

Row (Depth)

Enter fullscreen mode Exit fullscreen mode

If we store nodes using:

Column

↓

Row

↓

Values

Enter fullscreen mode Exit fullscreen mode

we can build the answer naturally.

Pattern Recognition

Whenever you see:

• Vertical Traversal
• Column-wise Traversal
• Horizontal Distance

Think:

BFS + Ordered Maps

Key Observation

Assign coordinates:

Root

↓

(Row = 0, Col = 0)

Enter fullscreen mode Exit fullscreen mode

Rules:

Left Child

↓

(Row + 1, Col - 1)

--------------------

Right Child

↓

(Row + 1, Col + 1)

Enter fullscreen mode Exit fullscreen mode

Store nodes as:

TreeMap<
    Column,
    TreeMap<
        Row,
        PriorityQueue<Values>
    >
>

Enter fullscreen mode Exit fullscreen mode

Optimal Approach

Step 1

Perform BFS.

Store:

(Node, Row, Column)

Enter fullscreen mode Exit fullscreen mode

Step 2

Insert into:

column

↓

row

↓

priority queue

Enter fullscreen mode Exit fullscreen mode

Step 3

Traverse:

Columns

↓

Rows

↓

Sorted Values

Enter fullscreen mode Exit fullscreen mode

Optimal Java Solution

class Pair {

    TreeNode node;
    int row;
    int col;

    Pair(TreeNode node,
         int row,
         int col) {

        this.node = node;
        this.row = row;
        this.col = col;
    }
}

class Solution {

    public List<List<Integer>> verticalTraversal(TreeNode root) {

        TreeMap<Integer,
        TreeMap<Integer,
        PriorityQueue<Integer>>> map =
                new TreeMap<>();

        Queue<Pair> q = new LinkedList<>();

        q.offer(new Pair(root, 0, 0));

        while (!q.isEmpty()) {

            Pair curr = q.poll();

            map.putIfAbsent(curr.col,
                    new TreeMap<>());

            map.get(curr.col)
               .putIfAbsent(curr.row,
                    new PriorityQueue<>());

            map.get(curr.col)
               .get(curr.row)
               .offer(curr.node.val);

            if (curr.node.left != null)

                q.offer(new Pair(
                        curr.node.left,
                        curr.row + 1,
                        curr.col - 1));

            if (curr.node.right != null)

                q.offer(new Pair(
                        curr.node.right,
                        curr.row + 1,
                        curr.col + 1));
        }

        List<List<Integer>> ans =
                new ArrayList<>();

        for (TreeMap<Integer,
             PriorityQueue<Integer>> rows
             : map.values()) {

            List<Integer> list =
                    new ArrayList<>();

            for (PriorityQueue<Integer> pq
                    : rows.values()) {

                while (!pq.isEmpty())

                    list.add(pq.poll());
            }

            ans.add(list);
        }

        return ans;
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

        3
       / \
      9  20
         / \
        15  7

Enter fullscreen mode Exit fullscreen mode

Coordinates:

9

↓

(-1,1)

3

↓

(0,0)

15

↓

(0,2)

20

↓

(1,1)

7

↓

(2,2)

Enter fullscreen mode Exit fullscreen mode

Vertical Order:

9

↓

3 15

↓

20

↓

7

Enter fullscreen mode Exit fullscreen mode

Answer:

[[9],[3,15],[20],[7]]

Enter fullscreen mode Exit fullscreen mode

Why BFS + Ordered Maps Work?

Every node is assigned:

Column

↓

Row

Enter fullscreen mode Exit fullscreen mode

TreeMap automatically sorts:

Columns

↓

Rows

Enter fullscreen mode Exit fullscreen mode

PriorityQueue handles nodes that share the same row and column.

Complexity Analysis

Metric Complexity Time Complexity O(N log N) Space Complexity O(N)

Interview One-Liner

Perform BFS while tracking row and column indices, then store nodes in nested TreeMaps with a PriorityQueue to maintain the required ordering.

Pattern Learned

BFS

↓

(Row, Column)

↓

Ordered Maps

↓

Vertical Traversal

Enter fullscreen mode Exit fullscreen mode

Similar Problems

• Vertical Order Traversal
• Top View
• Bottom View
• Vertical Sum
• Diagonal Traversal

Memory Trick

Think:

Node

↓

(Row, Column)

↓

TreeMap

↓

PriorityQueue

↓

Answer

Enter fullscreen mode Exit fullscreen mode

Mental Model

Tree

↓

Assign Coordinates

↓

Group By Column

↓

Sort By Row

↓

Output

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Vertical Order Traversal”

your brain should immediately think:

BFS + (Row, Column) Coordinates + TreeMap