Group a Tree's Values Level by Level
Solve this ProblemYou are given the root of a binary tree. Group the node values by level: the root alone forms the first group, its children (left to right) the second, their children the third, and so on. Return the groups from the top level to the bottom level.
You can find the groups by re-walking the tree once per level, but a queue does it in a single pass: it always holds the nodes of the level being processed, and the nodes it collects behind them form the next level.
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 - ◆
Return one list per level of the tree, from the root level downwards; inside a level, list the values from left to right. An empty tree gives an empty list of levels
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Walk the Tree Once per Level
BruteFirst find the height h of the tree. Then, for each level number from 0 to h − 1, walk the whole tree again with a helper that carries a "levels still to go down" counter: when the counter hits 0 the node is on the wanted level, so its value goes into that level's row; otherwise recurse into the left child and then the right child with the counter reduced by one. Visiting left before right keeps each row in left-to-right order. It is correct, but each of the h passes re-walks up to n nodes, so the time is O(n · h) — O(n²) on a tall, thin tree.
O(n · h)O(n)1class Solution {
2 public List<List<Integer>> levelGroups(TreeNode root) {
3 List<List<Integer>> levels = new ArrayList<>();
4 int h = height(root);
5 for (int depth = 0; depth < h; depth++) {
6 List<Integer> row = new ArrayList<>();
7 collect(root, depth, row);
8 levels.add(row);
9 }
10 return levels;
11 }
12
13 private int height(TreeNode node) {
14 if (node == null) return 0;
15 return 1 + Math.max(height(node.left), height(node.right));
16 }
17
18 private void collect(TreeNode node, int depth, List<Integer> row) {
19 if (node == null) return;
20 if (depth == 0) {
21 row.add(node.val);
22 return;
23 }
24 collect(node.left, depth - 1, row);
25 collect(node.right, depth - 1, row);
26 }
27}Optimal — Breadth-First With a Queue
OptimalUse a queue that always holds the nodes of the level about to be processed. Start with the root. Each round, note the queue's current size — that is exactly the number of nodes on this level — and take that many nodes off the front. Record each node's value in a fresh row and add its existing children to the back of the queue; those children make up the next level. After the inner loop the row is complete, so append it to the answer. Each node enters and leaves the queue once: O(n) time, and the queue never holds more than one or two levels, so the extra space is O(w) where w is the widest level.
O(n)O(w)1class Solution {
2 public List<List<Integer>> levelGroups(TreeNode root) {
3 List<List<Integer>> levels = new ArrayList<>();
4 if (root == null) return levels;
5 Queue<TreeNode> queue = new ArrayDeque<>();
6 queue.add(root);
7 while (!queue.isEmpty()) {
8 int size = queue.size();
9 List<Integer> row = new ArrayList<>();
10 for (int i = 0; i < size; i++) {
11 TreeNode node = queue.poll();
12 row.add(node.val);
13 if (node.left != null) queue.add(node.left);
14 if (node.right != null) queue.add(node.right);
15 }
16 levels.add(row);
17 }
18 return levels;
19 }
20}