Link Each Node to Its Right Neighbour
Solve this ProblemYou are given the root of a binary tree in which every node has, besides its value and its left and right children, an extra pointer called next (initially null). Fill in every next pointer so that it points to the node immediately to the right on the same level; the rightmost node of each level keeps next = null. Return the root.
A queue that processes the tree one level at a time makes this easy. The classic refinement uses no queue at all: the next links of one level are used to walk it while the links of the level below are being created.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; 0 ≤ node.val ≤ 1000 - ◆
The tree is given as its root node (null for an empty tree). Besides val, left and right, every node has a next pointer that starts as null - ◆
Set each node's next pointer to the node immediately to its right ON THE SAME LEVEL, or leave it null when the node is the rightmost of its level. Return the root - ◆
The result is checked level by level: for every node in level order (left to right within a level) the value of its next node is reported, or -1 if next is null
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Level-by-Level With a Queue
GoodProcess the tree level by level with a queue. Before each level, note the queue's size (the number of nodes on the level). While taking those nodes off the front, remember the previous node of the same level and point its next at the current node. The first node of every level has no previous node and the last node is never given a next, so it stays null. Children are queued for the following level. O(n) time, and the queue holds up to a whole level of nodes: O(w) extra space.
O(n)O(w)1class Solution {
2 public TreeNode linkNeighbors(TreeNode root) {
3 if (root == null) return null;
4 Queue<TreeNode> queue = new ArrayDeque<>();
5 queue.add(root);
6 while (!queue.isEmpty()) {
7 int size = queue.size();
8 TreeNode prev = null;
9 for (int i = 0; i < size; i++) {
10 TreeNode node = queue.poll();
11 if (prev != null) prev.next = node;
12 prev = node;
13 if (node.left != null) queue.add(node.left);
14 if (node.right != null) queue.add(node.right);
15 }
16 }
17 return root;
18 }
19}Optimal — Use the Links Already Built on the Level Above (O(1) Space)
OptimalNo queue is needed: the next pointers of one level can be used to walk it, and while walking it we build the next pointers of the level below. Keep levelStart, the leftmost node of the level being walked (initially the root). Walk that level through its next pointers; for every node, append its existing children to a chain that hangs off a throw-away dummy head (tail.next = child, then move tail). When the walk ends, the chain from dummy.next is the whole next level, already linked left-to-right — and its first node is the new levelStart. Repeat until a level has no nodes. Every node is visited once: O(n) time and only O(1) extra space (a dummy node and two pointers).
O(n)O(1)1class Solution {
2 public TreeNode linkNeighbors(TreeNode root) {
3 TreeNode levelStart = root;
4 while (levelStart != null) {
5 TreeNode dummy = new TreeNode(0);
6 TreeNode tail = dummy;
7 for (TreeNode cur = levelStart; cur != null; cur = cur.next) {
8 if (cur.left != null) {
9 tail.next = cur.left;
10 tail = tail.next;
11 }
12 if (cur.right != null) {
13 tail.next = cur.right;
14 tail = tail.next;
15 }
16 }
17 levelStart = dummy.next;
18 }
19 return root;
20 }
21}