Home › DSA › Company Practice

medium Binary Tree Vertical Order Traversal

Problem Statement

Given the root of the binary tree, return the 2D list containing the vertical order traversal of the binary tree.

A vertical order traversal of the tree is defined as a top to bottom, column by column traversal.

Note: If two nodes are in the same row and column, keep its order from left to right.

Examples

Example 1:

Input: A binary tree: [1,2,3,4,5,6,7]
Expected Output: [[4], [2], [1,5,6], [3], [7]]
Justification: Nodes 4, 2, 1 with 5 and 6, 3, and 7 are in separate vertical lines. The nodes in each vertical line are listed in the order they appear from top to bottom.

Example 2:

Input: A binary tree: [3,9,8,4,0,1,7]
Expected Output: [[4], [9], [3,0,1], [8], [7]]
Justification: Nodes are grouped based on their vertical positions. Lower nodes in the same vertical line follow the higher ones.

Example 3:

Input: A binary tree: [3,null,20,15,7]
Expected Output: [[3, 15], [20], [7]]
Justification: The tree is skewed to the right. The output reflects the vertical traversal from left to right.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Binary Tree Vertical Order Traversal (medium)

1. Why / judgment

Assign horizontal distance col: root 0, left col-1, right col+1. BFS so top-to-bottom and left-to-right within same level feeds each column list correctly. TreeMap/min-max col track for ordered columns. When-NOT: vertical order by value sort within col -> LC 987 harder; DFS needs sort by row.

2. Big-O derivation (K11)

O(n) visit; O(n) maps.
Output columns sorted by col key.
[1,2,3,4,5,6,7] -> [[4],[2],[1,5,6],[3],[7]].

3. Pattern + when-NOT (K12)

Name: BFS + COLUMN INDEX GROUPING

Recognition: nodes by vertical line left to right, top to bottom.

When-NOT: Need row-major only -> level order. Need sorted values in col -> extra sort.

4. Edge hand-run (K13)

null root -> []
skewed left -> many negative cols
tie same col same row: BFS left child first gives left-to-right

5. Interviewer follow-ups (model answers)

Q1. Why BFS not DFS?
A: BFS naturally top-to-bottom; DFS needs explicit row and sort.

Q2. HashMap + min/max vs TreeMap?
A: HashMap O(n) then emit min..max; TreeMap log factor.

Q3. Can cols be sparse?
A: Yes; still iterate min..max contiguous integers.

6. Short drills

Drill: single node
Drill: only left children
Drill: code queue pair (node,col)

✅ Solution Binary Tree Vertical Order Traversal

Problem Statement

Given the root of the binary tree, return the 2D list containing the vertical order traversal of the binary tree.

A vertical order traversal of the tree is defined as a top to bottom, column by column traversal.

Note: If two nodes are in the same row and column, keep its order from left to right.

Examples

Example 1:

Input: A binary tree: [1,2,3,4,5,6,7]
Expected Output: [[4], [2], [1,5,6], [3], [7]]
Justification: Nodes 4, 2, 1 with 5 and 6, 3, and 7 are in separate vertical lines. The nodes in each vertical line are listed in the order they appear from top to bottom.

Example 2:

Input: A binary tree: [3,9,8,4,0,1,7]
Expected Output: [[4], [9], [3,0,1], [8], [7]]
Justification: Nodes are grouped based on their vertical positions. Lower nodes in the same vertical line follow the higher ones.

Example 3:

Input: A binary tree: [3,null,20,15,7]
Expected Output: [[3, 15], [20], [7]]
Justification: The tree is skewed to the right. The output reflects the vertical traversal from left to right.

Solution

To solve this problem, we'll use a breadth-first search (BFS) strategy combined with a tracking mechanism for the horizontal positions (or 'columns') of the nodes. BFS is ideal because it naturally explores the tree level by level, ensuring that we process nodes on the same level in the correct order.

We'll use a queue to facilitate the BFS, and a hashmap (or dictionary) to keep track of the nodes' column indices. The key point is to associate each node with its respective column index, allowing us to group nodes that are vertically aligned. We'll also keep track of the minimum and maximum column indices encountered, which will guide us in forming the final output list in the correct left-to-right vertical order.

Step-by-step Algorithm

Initialize a queue to perform BFS and a hashmap to store node values grouped by their column index.
Start with the root node in the queue, with a column index of 0.
Perform BFS:
- Dequeue a node from the queue and record its value in the hashmap under its column index.
- If the node has a left child, enqueue it with a column index one less than the current node.
- If the node has a right child, enqueue it with a column index one more than the current node.
- Update the minimum and maximum column indices when necessary.
After completing BFS, iterate from the minimum to the maximum column index, and append the corresponding list of node values from the hashmap to the output list.

Algorithm Walkthrough

Consider the input [1,2,3,4,5,6,7]. Let's walk through the algorithm:

Start with root node 1 at column index 0.
Enqueue left child 2 with column index -1, and right child 3 with column index +1.
Continue BFS:
- For node 2, enqueue its children 4 and 5 with column indices -2 and 0, respectively.
- For node 3, enqueue its children 6 and 7 with column indices 0 and +2, respectively.
The final column index hashmap looks like: {-2: [4], -1: [2], 0: [1, 5, 6], 1: [3], 2: [7]}.
Iterating over the column indices from -2 to 2, we get the final output: [[4], [2], [1,5,6], [3], [7]].

Code

java

import java.util.*;

// TreeNode class definition
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int x) {
//         val = x;
//     }

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

// Pair class to associate a node with its column index
class Pair<K, V> {

  private K key;
  private V value;

  public Pair(K key, V value) {
    this.key = key;
    this.value = value;
  }

  public K getKey() {
    return key;
  }

  public V getValue() {
    return value;
  }
}

class Solution {

  public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Map<Integer, List<Integer>> columnTable = new HashMap<>();
    Queue<Pair<TreeNode, Integer>> queue = new ArrayDeque<>();
    int column = 0;
    int minColumn = 0, maxColumn = 0;

    // Start BFS with the root node
    queue.offer(new Pair<>(root, column));

    while (!queue.isEmpty()) {
      Pair<TreeNode, Integer> p = queue.poll();
      root = p.getKey();
      column = p.getValue();

      if (root != null) {
        // If this column has not been seen before, create a new List
        columnTable.putIfAbsent(column, new ArrayList<>());
        // Add the node's value to the column's list
        columnTable.get(column).add(root.val);
        // Update the min and max column indices
        minColumn = Math.min(minColumn, column);
        maxColumn = Math.max(maxColumn, column);

        // Enqueue child nodes with their respective column indices
        queue.offer(new Pair<>(root.left, column - 1));
        queue.offer(new Pair<>(root.right, column + 1));
      }
    }

    // Construct the final list by combining lists from each column
    for (int i = minColumn; i <= maxColumn; i++) {
      result.add(columnTable.get(i));
    }

    return result;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test cases
    // Example 1
    TreeNode root1 = new TreeNode(
      1,
      new TreeNode(2, new TreeNode(4), new TreeNode(5)),
      new TreeNode(3, new TreeNode(6), new TreeNode(7))
    );
    System.out.println(solution.verticalOrder(root1));

    // Example 2
    TreeNode root2 = new TreeNode(
      3,
      new TreeNode(9, new TreeNode(4), new TreeNode(0)),
      new TreeNode(8, new TreeNode(1), new TreeNode(7))
    );
    System.out.println(solution.verticalOrder(root2));

    // Example 3
    TreeNode root3 = new TreeNode(
      3,
      null,
      new TreeNode(20, new TreeNode(15), new TreeNode(7))
    );
    System.out.println(solution.verticalOrder(root3));
  }
}

Complexity Analysis

Time Complexity: The algorithm's time complexity is O(N), where N is the number of nodes in the tree. This is because each node is processed exactly once during the BFS.
Space Complexity: The space complexity is also O(N), as we store all nodes in the hashmap and the queue at

🎯 STRICT STANDOUT — Solution Binary Tree Vertical Order Traversal

1. Why / judgment

Queue of (node, col). HashMap col to List. Track minCol maxCol. BFS order guarantees top-to-bottom. Emit lists for col in min..max. Hand-run tree [1,2,3,4,5,6,7] columns as stated.

2. Big-O derivation (K11)

O(n) time space
Skewed O(n) columns
Balanced width O(n)

3. Pattern + when-NOT (K12)

Name: VERTICAL BFS GROUPING

Recognition: column order traversal.

When-NOT: LC987 sorts by row then val — extra keys.

4. Edge hand-run (K13)

root only [[root]]
missing children gaps still dense cols integers

5. Interviewer follow-ups (model answers)

Q1. Queue empty end?
A: Standard BFS termination.

Q2. Array index shift by -minCol?
A: Yes alternative to map.

Q3. DFS order bug?
A: Without sorting by depth, DFS can put lower node before upper in same col.

6. Short drills

Drill: code full solution
Drill: same col two nodes different depth
Drill: negative cols

🧩 Pattern · Trees

Recognize it: Hierarchical data → recurse on children; BFS (queue) for level-order, DFS (recursion) for paths.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Binary Tree Vertical Order Traversal? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Binary Tree Vertical Order Traversal** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Binary Tree Vertical Order Traversal** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Binary Tree Vertical Order Traversal**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Binary Tree Vertical Order Traversal**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Edit Distance Maximum Length of Subarray With Po →