Vertical Order Traversal of a Binary Tree

Share

Given the root of a binary tree, return the vertical order traversal of its nodes. For each position (col), nodes are ordered top to bottom, then left to right.

Example 1
Input: root=[3,9,20,null,null,15,7] → Output: [[9],[3,15],[20],[7]]
Example 2
Input: root=[1,2,3,4,5,6,7] → Output: [[4],[2],[1,5,6],[3],[7]]

Solution Approach

DFS collecting (col, row, val) triples. Sort by col, then row, then val. Group by column.

  • DFS: dfs(node, col, row) collects (col, row, val).
  • Sort list by (col, row, val).
  • Group consecutive same-col entries into sublists.
Java
import java.util.*;

class Solution {
    List<int[]> nodes = new ArrayList<>();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        nodes.sort((a, b) -> a[0] != b[0] ? a[0]-b[0] : a[1] != b[1] ? a[1]-b[1] : a[2]-b[2]);
        List<List<Integer>> result = new ArrayList<>();
        int prevCol = Integer.MIN_VALUE;
        for (int[] node : nodes) {
            if (node[0] != prevCol) { result.add(new ArrayList<>()); prevCol = node[0]; }
            result.get(result.size()-1).add(node[2]);
        }
        return result;
    }
    private void dfs(TreeNode node, int col, int row) {
        if (node == null) return;
        nodes.add(new int[]{col, row, node.val});
        dfs(node.left, col-1, row+1); dfs(node.right, col+1, row+1);
    }
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)