Loading problem...
Given the root of a binary tree, compute the columnar traversal of the tree, which organizes nodes based on their horizontal (column) and vertical (depth) positions.
Consider each node to have a position coordinate (depth, column) where:
The columnar traversal produces a list of sublists, where each sublist contains all nodes from a single column, ordered from the leftmost column to the rightmost column. Within each column, nodes are arranged from top to bottom (by depth). If multiple nodes share the same position (identical depth and column), they should be sorted by their node values in ascending order.
Return the complete columnar traversal of the binary tree as a 2D list.
root = [3,9,20,null,null,15,7][[9],[3,15],[20],[7]]Column -1 contains only node 9. Column 0 contains nodes 3 (at depth 0) and 15 (at depth 2), listed top to bottom. Column 1 contains only node 20. Column 2 contains only node 7.
root = [1,2,3,4,5,6,7][[4],[2],[1,5,6],[3],[7]]Column -2 has node 4. Column -1 has node 2. Column 0 has nodes 1, 5, and 6 — since 1 is at depth 0, it comes first; nodes 5 and 6 are both at position (2, 0), so they are sorted by value: 5 before 6. Column 1 has node 3. Column 2 has node 7.
root = [1,2,3,4,6,5,7][[4],[2],[1,5,6],[3],[7]]This is identical to the previous example but with nodes 5 and 6 swapped in the input tree structure. The output remains the same because nodes at the same position are sorted by their values, so 5 still appears before 6.
Constraints