Read the Tree Column by Column
Solve this ProblemYou are given the root of a binary tree. Place the root at position (row 0, column 0); a left child sits one row lower and one column to the left of its parent, and a right child one row lower and one column to the right. Return the node values grouped by column, from the leftmost occupied column to the rightmost. Inside a column list the values from top to bottom; nodes that share both row and column are ordered by value, smaller first.
Handling one column at a time re-walks the tree over and over. Tagging every node with its position, sorting the tags, and grouping by column does the whole job in a single walk plus a sort.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; −100 ≤ node.val ≤ 100 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
Give each node a position (row, column): the root is (0, 0); a left child is one row down and one column to the LEFT of its parent (row + 1, column − 1); a right child is one row down and one column to the RIGHT (row + 1, column + 1) - ◆
Return one list per occupied column, from the leftmost column to the rightmost. Inside a column list the values from the top row to the bottom row; if two nodes share the same row and column, the smaller value comes first. An empty tree gives an empty list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Rescan the Whole Tree for Every Column
BruteFirst find the range of columns the tree occupies (a walk that tracks the column: left child −1, right child +1). Then, for every column in that range, walk the entire tree again, collecting the (row, value) pairs of the nodes that sit in exactly that column, and sort them by row and then by value. The sorted values are that column's list. Correct, but every column costs a full walk, so with w columns the work is O(n · w) plus the sorting.
O(n · w · log n)O(n)1class Solution {
2 public List<List<Integer>> columnsLeftToRight(TreeNode root) {
3 List<List<Integer>> result = new ArrayList<>();
4 if (root == null) return result;
5 int[] range = {0, 0};
6 span(root, 0, range);
7 for (int col = range[0]; col <= range[1]; col++) {
8 List<int[]> cells = new ArrayList<>();
9 gather(root, 0, 0, col, cells);
10 cells.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
11 List<Integer> column = new ArrayList<>();
12 for (int[] cell : cells) column.add(cell[1]);
13 result.add(column);
14 }
15 return result;
16 }
17
18 private void span(TreeNode node, int col, int[] range) {
19 if (node == null) return;
20 range[0] = Math.min(range[0], col);
21 range[1] = Math.max(range[1], col);
22 span(node.left, col - 1, range);
23 span(node.right, col + 1, range);
24 }
25
26 private void gather(TreeNode node, int row, int col, int target, List<int[]> cells) {
27 if (node == null) return;
28 if (col == target) cells.add(new int[]{row, node.val});
29 gather(node.left, row + 1, col - 1, target, cells);
30 gather(node.right, row + 1, col + 1, target, cells);
31 }
32}Optimal — Tag Every Node Once, Sort, and Group by Column
OptimalWalk the tree once and record a triple (column, row, value) for every node — the column changes by −1 going left and +1 going right, the row by +1 going down. Sort all triples by column, then row, then value. That single sort already puts every column's nodes together, in the required top-to-bottom order with ties broken by value. Finally scan the sorted triples and start a new list whenever the column changes. One walk plus one sort: O(n log n) time and O(n) space.
O(n log n)O(n)1class Solution {
2 public List<List<Integer>> columnsLeftToRight(TreeNode root) {
3 List<int[]> cells = new ArrayList<>();
4 collect(root, 0, 0, cells);
5 cells.sort((a, b) -> {
6 if (a[0] != b[0]) return a[0] - b[0];
7 if (a[1] != b[1]) return a[1] - b[1];
8 return a[2] - b[2];
9 });
10 List<List<Integer>> result = new ArrayList<>();
11 int prevCol = Integer.MIN_VALUE;
12 for (int[] cell : cells) {
13 if (cell[0] != prevCol) {
14 result.add(new ArrayList<>());
15 prevCol = cell[0];
16 }
17 result.get(result.size() - 1).add(cell[2]);
18 }
19 return result;
20 }
21
22 private void collect(TreeNode node, int col, int row, List<int[]> cells) {
23 if (node == null) return;
24 cells.add(new int[]{col, row, node.val});
25 collect(node.left, col - 1, row + 1, cells);
26 collect(node.right, col + 1, row + 1, cells);
27 }
28}