Vertical Order Traversal of Binary Tree in DSA Java

Mental Model

We group tree nodes by their vertical columns and list nodes top to bottom in each column.

Analogy: Imagine standing in front of a tree and looking straight at it. Nodes that line up vertically form a column. We want to list nodes column by column from left to right.

      1
     / \
    2   3
   / \   \
  4   5   6

Columns:
-2: 4
-1: 2
 0: 1 -> 5
 1: 3
 2: 6

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6

Goal: Print nodes grouped by vertical columns from left to right, top to bottom in each column.

Step 1: Start at root (1) with column 0 and row 0

Column 0: [ (row 0, val 1) ]

Why: Root is the center column and top row

Step 2: Go left child (2) at column -1, row 1

Column -1: [ (row 1, val 2) ]
Column 0: [ (row 0, val 1) ]

Why: Left child is one column left and one row down

Step 3: Go left child of 2 (4) at column -2, row 2

Column -2: [ (row 2, val 4) ]
Column -1: [ (row 1, val 2) ]
Column 0: [ (row 0, val 1) ]

Why: Left child moves one more column left and one more row down

Step 4: Go right child of 2 (5) at column 0, row 2

Column -2: [ (row 2, val 4) ]
Column -1: [ (row 1, val 2) ]
Column 0: [ (row 0, val 1), (row 2, val 5) ]

Why: Right child moves one column right and one row down

Step 5: Go right child of root (3) at column 1, row 1

Column -2: [ (row 2, val 4) ]
Column -1: [ (row 1, val 2) ]
Column 0: [ (row 0, val 1), (row 2, val 5) ]
Column 1: [ (row 1, val 3) ]

Why: Right child of root is one column right and one row down

Step 6: Go right child of 3 (6) at column 2, row 2

Column -2: [ (row 2, val 4) ]
Column -1: [ (row 1, val 2) ]
Column 0: [ (row 0, val 1), (row 2, val 5) ]
Column 1: [ (row 1, val 3) ]
Column 2: [ (row 2, val 6) ]

Why: Right child moves one more column right and one more row down

Step 7: Sort nodes in each column by row, then by value if tie

Column -2: [4]
Column -1: [2]
Column 0: [1, 5]
Column 1: [3]
Column 2: [6]

Why: We want top to bottom order in each vertical column

Result:

Vertical order traversal:
4
2
1 5
3
6

Annotated Code

DSA Java

import java.util.*;

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

public class VerticalOrderTraversal {

    static class NodeInfo {
        int row, val;
        NodeInfo(int row, int val) {
            this.row = row;
            this.val = val;
        }
    }

    public static List<List<Integer>> verticalTraversal(TreeNode root) {
        // Map column -> list of (row, val)
        TreeMap<Integer, List<NodeInfo>> map = new TreeMap<>();
        dfs(root, 0, 0, map);

        List<List<Integer>> result = new ArrayList<>();
        for (int col : map.keySet()) {
            List<NodeInfo> nodes = map.get(col);
            // Sort by row, then val
            nodes.sort((a, b) -> a.row != b.row ? a.row - b.row : a.val - b.val);
            List<Integer> colVals = new ArrayList<>();
            for (NodeInfo ni : nodes) {
                colVals.add(ni.val);
            }
            result.add(colVals);
        }
        return result;
    }

    private static void dfs(TreeNode node, int col, int row, TreeMap<Integer, List<NodeInfo>> map) {
        if (node == null) return;
        map.computeIfAbsent(col, k -> new ArrayList<>()).add(new NodeInfo(row, node.val));
        dfs(node.left, col - 1, row + 1, map);
        dfs(node.right, col + 1, row + 1, map);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        List<List<Integer>> verticalOrder = verticalTraversal(root);
        for (List<Integer> col : verticalOrder) {
            for (int val : col) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }
}

map.computeIfAbsent(col, k -> new ArrayList<>()).add(new NodeInfo(row, node.val));

Add current node info to the list for its column

dfs(node.left, col - 1, row + 1, map);

Traverse left child one column left and one row down

dfs(node.right, col + 1, row + 1, map);

Traverse right child one column right and one row down

nodes.sort((a, b) -> a.row != b.row ? a.row - b.row : a.val - b.val);

Sort nodes in column by row, then by value if rows tie

Output

4 

2 

1 5 

3 

6 

Complexity Analysis

Time: O(n log n) because we visit all n nodes and sort nodes in each column

Space: O(n) to store all nodes in the map and recursion stack

vs Alternative: Naive approaches may use BFS with extra bookkeeping but sorting is still needed; this DFS with map is clean and efficient

Edge Cases

Empty tree

Returns empty list without error

DSA Java

if (node == null) return;

Tree with single node

Returns list with one column containing that node

DSA Java

map.computeIfAbsent(col, k -> new ArrayList<>()).add(new NodeInfo(row, node.val));

Multiple nodes in same row and column

Nodes sorted by value to maintain order

DSA Java

nodes.sort((a, b) -> a.row != b.row ? a.row - b.row : a.val - b.val);

When to Use This Pattern

When a problem asks to print tree nodes column by column vertically, use vertical order traversal with column and row tracking to group and sort nodes.

Common Mistakes

Mistake: Not tracking row to sort nodes top to bottom within the same column
Fix: Include row information and sort nodes by row before output

Mistake: Using a HashMap instead of TreeMap causing unordered columns
Fix: Use TreeMap to keep columns sorted from left to right

Summary

Groups binary tree nodes by vertical columns and lists them top to bottom in each column.

Use when you need to print or process tree nodes column-wise from left to right.

Track column and row indices during traversal and sort nodes by row and value within each column.

Practice

1. What does Vertical Order Traversal of a binary tree mean?

easy

A. Nodes are grouped by their vertical columns from left to right

B. Nodes are visited in preorder (root, left, right)

C. Nodes are visited level by level from top to bottom

D. Nodes are grouped by their horizontal rows from top to bottom

Solution

1. Step 1: Understand vertical columns in a tree

   Vertical order groups nodes by their horizontal distance from the root, called columns.

2. Step 2: Define vertical order traversal

   Nodes in the same vertical column are collected and output from leftmost to rightmost column.

3. Final Answer:

   Nodes are grouped by their vertical columns from left to right -> Option A

4. Quick Check:

   Vertical order = group by columns [OK]

Hint: Think columns from left to right, not rows or preorder [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking vertical order is preorder or inorder traversal
• Mixing horizontal rows with vertical columns

2. Which Java data structure is best to store nodes grouped by their vertical column during vertical order traversal?

easy

A. ArrayList<Integer>

B. HashMap

C. Stack<Integer>

D. Queue<Integer>

Solution

1. Step 1: Identify need to map columns to nodes

   We need to group nodes by their vertical column index, so a map from column to list of nodes is needed.

2. Step 2: Choose suitable Java data structure

   A HashMap with key as column index (Integer) and value as list of nodes (List<Integer>) fits perfectly.

3. Final Answer:

   HashMap -> Option B

4. Quick Check:

   Map column to nodes = HashMap [OK]

Hint: Use map from column index to list of nodes [OK]

Common Mistakes:

• Using ArrayList alone without mapping columns
• Using Stack or Queue which don't map keys to lists
• Confusing data structures for traversal order

3. What is the vertical order traversal output of this binary tree?

    1
   / \
  2   3
 / \   \
4   5   6

medium

A. [4, 2, 1, 3, 5, 6]

B. [1, 2, 3, 4, 5, 6]

C. [4, 2, 1, 5, 3, 6]

D. [4, 5, 2, 1, 3, 6]

Solution

1. Step 1: Assign column indices to nodes

   Root 1 is at column 0. Left child 2 at -1, right child 3 at +1. 4 at -2, 5 at 0, 6 at +2.

2. Step 2: Collect nodes column-wise from left to right

   Columns: -2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]. Combine: [4, 2, 1, 5, 3, 6]

3. Final Answer:

   [4, 2, 1, 5, 3, 6] -> Option C

4. Quick Check:

   Columns left to right = [4,2,1,5,3,6] [OK]

Hint: Label columns from root 0, left -1, right +1, then read left to right [OK]

Common Mistakes:

• Ignoring multiple nodes in same column order
• Mixing preorder or inorder output with vertical order
• Not assigning correct column indices

4. Given this Java snippet for vertical order traversal, what is the error?

Map map = new HashMap<>();
Queue> queue = new LinkedList<>();
queue.add(new Pair(root, 0));
while (!queue.isEmpty()) {
  Pair p = queue.poll();
  TreeNode node = p.getKey();
  int col = p.getValue();
  map.putIfAbsent(col, new ArrayList<>());
  map.get(col).add(node.val);
  if (node.left != null) queue.add(new Pair(node.left, col - 1));
  if (node.right != null) queue.add(new Pair(node.right, col + 1));
}

medium

A. Pair class is not imported or defined

B. Queue should be a Stack for correct traversal

C. map.putIfAbsent should be replaced with map.put

D. col should be incremented for left child, not decremented

Solution

1. Step 1: Check usage of Pair class

   The code uses Pair but Java does not have Pair by default; it must be imported or defined.

2. Step 2: Identify missing import or definition

   Without importing javafx.util.Pair or defining a custom Pair class, this code will not compile.

3. Final Answer:

   Pair class is not imported or defined -> Option A

4. Quick Check:

   Missing Pair class causes compile error [OK]

Hint: Check if all classes like Pair are imported or defined [OK]

Common Mistakes:

• Assuming Pair is built-in in Java standard library
• Using Stack instead of Queue for BFS traversal
• Incorrect column increment direction for left child

5. How would you modify vertical order traversal to output nodes sorted by row and then value within each vertical column? Choose the best approach.

hard

A. Use a Queue and print nodes as they are visited

B. Use a HashMap and sort each list after traversal

C. Use a Stack to store nodes and pop in sorted order

D. Use a TreeMap> to map column -> row -> sorted nodes

Solution

1. Step 1: Understand sorting by row and value in vertical columns

   We need to group nodes by column, then by row, and sort nodes with same row by value.

2. Step 2: Choose data structure supporting nested sorting

   TreeMap for columns and rows keeps keys sorted. PriorityQueue stores nodes sorted by value. So TreeMap> fits.

3. Final Answer:

   Use a TreeMap> to map column -> row -> sorted nodes -> Option D

4. Quick Check:

   Nested TreeMaps + PriorityQueue = sorted vertical order [OK]

Hint: Use nested TreeMaps and PriorityQueue for sorted vertical order [OK]

Common Mistakes:

• Sorting lists after traversal loses row info
• Using Stack or Queue which don't sort nodes
• Ignoring row sorting within columns