Course4all
Join us on telegram
Home/dsa/Trees/Vertical Order Traversal

Vertical Order Traversal

Master this topic with zero to advance depth.

Vertical Order Traversal

Vertical columns.

Hard
Approach 1

Level I: DFS with List of Nodes per Column

Intuition

We can perform a DFS and for each node, we pass down its column index. We store nodes in a Map of col -> List<Node>. After traversal, we sort the keys (cols) and then sort each list of nodes by their depth and value.

Logic

  1. DFS with (node, col, depth).
  2. Store in Map<Integer, List<int[]>> (col -> [depth, val]).
  3. Sort.
⏱ O(N log N)💾 O(N)

Detailed Dry Run

Col -1: [2]. Col 0: [1, 3]. Col 1: [4]. Sorting ensures correct ordering.

java
public class Main {
    Map<Integer, List<int[]>> map = new TreeMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        List<List<Integer>> res = new ArrayList<>();
        for (int col : map.keySet()) {
            List<int[]> nodes = map.get(col);
            Collections.sort(nodes, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
            List<Integer> curr = new ArrayList<>();
            for (int[] n : nodes) curr.add(n[1]);
            res.add(curr);
        }
        return res;
    }
    private void dfs(TreeNode n, int c, int d) {
        if (n == null) return;
        map.computeIfAbsent(c, k -> new ArrayList<>()).add(new int[]{d, n.val});
        dfs(n.left, c - 1, d + 1); dfs(n.right, c + 1, d + 1);
    }
}
Approach 2

Level II: BFS with Sorting

Intuition

BFS naturally processes nodes level by level. By adding column information, we can group nodes. However, since multiple nodes can have the same (col, depth), we still need sorting for nodes in the same cell.

Logic

  • Queue of (node, col, depth).
  • Map of col -> List of (depth, val).
  • Sort result lists.
⏱ O(N log N)💾 O(N)

Detailed Dry Run

Similar to Level I but uses Queue.

java
public class Main {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<int[]>> map = new TreeMap<>();
        Queue<Object[]> q = new LinkedList<>();
        q.add(new Object[]{root, 0, 0});
        while (!q.isEmpty()) {
            Object[] curr = q.poll();
            TreeNode n = (TreeNode)curr[0];
            int c = (int)curr[1], d = (int)curr[2];
            map.computeIfAbsent(c, k -> new ArrayList<>()).add(new int[]{d, n.val});
            if (n.left != null) q.add(new Object[]{n.left, c - 1, d + 1});
            if (n.right != null) q.add(new Object[]{n.right, c + 1, d + 1});
        }
        // Sort as in Level I
        return null; // Placeholder
    }
}
Approach 3

Level III: Optimal (BFS + Range Tracking)

Intuition

Thought Process

We want to group nodes by their vertical column. Root is col=0. Left child is col-1, Right is col+1.

Since we need to return results from left-to-right, we can track the min and max column indices during BFS. This avoids sorting at the end.

Logic

  1. Use BFS with a Queue of (Node, col).
  2. Store nodes in a Map: Map<Integer, List<Integer>> (col -> list of vals).
  3. Keep track of minCol and maxCol.
  4. Loop from minCol to maxCol to collect results.
⏱ O(N)💾 O(N)

Detailed Dry Run

NodeColMinMaxMap
3000{0: [3]}
9-1-10{0: [3], -1: [9]}
201-11{0: [3], -1: [9], 1: [20]}
java
public class Main {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Map<Integer, List<Integer>> map = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>();
        Queue<Integer> cols = new LinkedList<>();
        q.add(root);
        cols.add(0);
        int min = 0, max = 0;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            int col = cols.poll();
            if (!map.containsKey(col)) map.put(col, new ArrayList<>());
            map.get(col).add(node.val);
            if (node.left != null) {
                q.add(node.left);
                cols.add(col - 1);
                min = Math.min(min, col - 1);
            }
            if (node.right != null) {
                q.add(node.right);
                cols.add(col + 1);
                max = Math.max(max, col + 1);
            }
        }
        for (int i = min; i <= max; i++) res.add(map.get(i));
        return res;
    }
}
← Previous QuestionFind Duplicate Subtrees
Next Question →Construct Binary Tree from Preorder and Postorder