Vertical Order Traversal means we must print nodes column by column, from leftmost vertical line to rightmost. But unlike the simpler vertical order problem, this one has strict ordering rules.

Given a binary tree, return the vertical traversal such that:

1. Nodes are grouped by their column index (x-coordinate)
2. Columns are ordered from left to right
3. Within each column, nodes are ordered:
   • first by row index (y-coordinate, top to bottom)
   • if row is the same, then by node value (ascending)

Example:

Input:
       3
      / \
     9   20
         / \
        15  7

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

---

How Coordinates Work

We treat the tree as a grid:

• Root has coordinates (x = 0, y = 0)
• Left child moves:
  • x – 1 (left column)
  • y + 1 (one row down)
• Right child moves:
  • x + 1 (right column)
  • y + 1 (one row down)

Example coordinate mapping:

       3(0,0)
      /      \
  9(-1,1)   20(1,1)
            /      \
     15(0,2)      7(2,2)

Now sorting works based on:

1. x (column)
2. y (row)
3. value

---

Logic Explained in Simple English

To solve the problem cleanly:

1. Traverse the tree (DFS or BFS)
2. While visiting each node, record:
   • x position (column)
   • y position (row)
   • node value
3. Store all nodes in a list of triples: (x, y, value)
4. After traversal, sort the list following the rules:
   • by x ascending
   • if x same, by y ascending
   • if x and y same, by value ascending
5. Group values by column (x)
6. Return grouped list

Why this works:

• Traversal assigns coordinates
• Sorting enforces ordering rules
• Grouping produces final output format

---

Step-by-Step Solution Approach

Step 1: Create a list to store node information

Each entry looks like:
[column, row, value]

Step 2: DFS traversal carrying x and y

Start at root with (0,0)

Step 3: Append node info as you traverse

Left child shifts (x – 1, y + 1)
Right child shifts (x + 1, y + 1)

Step 4: Sort list

Use comparator with 3 sorting levels

Step 5: Build result list

Group by column

---

Java Implementation

class Solution {
    private static class NodeInfo {
        int x, y, val;
        NodeInfo(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<NodeInfo> nodes = new ArrayList<>();
        dfs(root, 0, 0, nodes);

        Collections.sort(nodes, (a, b) -> {
            if (a.x != b.x) return a.x - b.x;
            if (a.y != b.y) return a.y - b.y;
            return a.val - b.val;
        });

        List<List<Integer>> result = new ArrayList<>();
        int prevX = Integer.MIN_VALUE;

        for (NodeInfo info : nodes) {
            if (info.x != prevX) {
                result.add(new ArrayList<>());
                prevX = info.x;
            }
            result.get(result.size() - 1).add(info.val);
        }

        return result;
    }

    private void dfs(TreeNode node, int x, int y, List<NodeInfo> nodes) {
        if (node == null) return;
        nodes.add(new NodeInfo(x, y, node.val));
        dfs(node.left, x - 1, y + 1, nodes);
        dfs(node.right, x + 1, y + 1, nodes);
    }
}

---

Dry Run Example

Tree:

       3
      / \
     9   20
         / \
        15  7

DFS traversal collects:

(0,0,3)
(-1,1,9)
(1,1,20)
(0,2,15)
(2,2,7)

After sorting by rules:

1. x ascending
2. y ascending
3. value ascending

Sorted list becomes:

(-1,1,9)
(0,0,3)
(0,2,15)
(1,1,20)
(2,2,7)

Group by x:

x = -1 → [9]
x = 0 → [3,15]
x = 1 → [20]
x = 2 → [7]

Final Result:

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

---

Time and Space Complexity

Time Complexity

O(n log n)
Reason:

• Traversal takes O(n)
• Sorting node list takes O(n log n)

Space Complexity

O(n)
Reason:

• Storing node coordinate list

---

Common Mistakes and How to Avoid Them

Mistake 1: Only sorting by column

But row and value ordering must also be handled.

Mistake 2: Using BFS without tracking coordinates properly

Must maintain x and y for each node.

Mistake 3: Grouping before sorting

Sorting must come first.

Mistake 4: Assuming tree shape is balanced

Traversal must work for skewed trees.

Mistake 5: Using HashMap ordering

Maps do not guarantee left-to-right ordering.