Jaspreet singh

Posted on Jul 5

Vertical Order Traversal

#algorithms #computerscience #interview #leetcode

leetcode.com

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)

If we store nodes using:

Column

↓

Row

↓

Values

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)

Rules:

Left Child

↓

(Row + 1, Col - 1)

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

Right Child

↓

(Row + 1, Col + 1)

Store nodes as:

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

Optimal Approach

Step 1

Perform BFS.

Store:

(Node, Row, Column)

Step 2

Insert into:

column

↓

row

↓

priority queue

Step 3

Traverse:

Columns

↓

Rows

↓

Sorted Values

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;
    }
}

Dry Run

Coordinates:

9

↓

(-1,1)

3

↓

(0,0)

15

↓

(0,2)

20

↓

(1,1)

7

↓

(2,2)

Vertical Order:

Answer:

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

Why BFS + Ordered Maps Work?

Every node is assigned:

Column

↓

Row

TreeMap automatically sorts:

Columns

↓

Rows

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

Memory Trick