Populating Next Right Pointers in Each Node
Wire each node's `next` pointer to its right neighbor in a perfect binary tree using O(1) extra space.
3 min read
tree bfs linked-list
Problem#
In a perfect binary tree, set each node’s next pointer to its level-right neighbor. The rightmost node’s next stays nullptr. Use constant extra space beyond the implicit tree.
Examples#
[1,2,3,4,5,6,7]→ next chains1 -> null,2 -> 3 -> null,4 -> 5 -> 6 -> 7 -> null.[]→[].
Constraints#
0 <= n <= 2^12 - 1. Tree is perfect.
Hints#
Hint 1
Once a level is wired, you can traverse it like a linked list and wire the next level’s pairs for free.
Hint 2
A perfect tree means every internal node has both children — no null guards needed during wiring.
Approach#
BFS — queue + size snapshot wires neighbors per level. O(n) time, O(n) space.
Level-link sweep — use already-set
next pointers on level k as a linked list to wire level k+1. O(1) extra space. For each node on the current level, link its left child to its right child, and its right child to the left child of node->next if it exists.
Solution#
class Solution {public: Node* connect(Node* root) { Node* leftmost = root; while (leftmost && leftmost->left) { Node* cur = leftmost; while (cur) { cur->left->next = cur->right; if (cur->next) cur->right->next = cur->next->left; cur = cur->next; } leftmost = leftmost->left; } return root; }};func connect(root *Node) *Node { leftmost := root for leftmost != nil && leftmost.Left != nil { cur := leftmost for cur != nil { cur.Left.Next = cur.Right if cur.Next != nil { cur.Right.Next = cur.Next.Left } cur = cur.Next } leftmost = leftmost.Left } return root}from typing import Optional
class Solution: def connect(self, root: Optional['Node']) -> Optional['Node']: leftmost = root while leftmost and leftmost.left: cur = leftmost while cur: cur.left.next = cur.right if cur.next: cur.right.next = cur.next.left cur = cur.next leftmost = leftmost.left return rootfunction connect(root) { let leftmost = root; while (leftmost && leftmost.left) { let cur = leftmost; while (cur) { cur.left.next = cur.right; if (cur.next) cur.right.next = cur.next.left; cur = cur.next; } leftmost = leftmost.left; } return root;}class Solution { public Node connect(Node root) { Node leftmost = root; while (leftmost != null && leftmost.left != null) { Node cur = leftmost; while (cur != null) { cur.left.next = cur.right; if (cur.next != null) cur.right.next = cur.next.left; cur = cur.next; } leftmost = leftmost.left; } return root; }}function connect(root: TreeNode | null): TreeNode | null { let leftmost: TreeNode | null = root; while (leftmost && leftmost.left) { let cur: TreeNode | null = leftmost; while (cur) { cur.left!.next = cur.right; if (cur.next) cur.right!.next = cur.next.left; cur = cur.next; } leftmost = leftmost.left; } return root;}Editorial#
The invariant: when the outer loop visits leftmost, every node on that level already has its next wired (level 0 trivially has just root). Using those pointers, we wire children pairs left-to-right without recursion or a queue. Perfect-tree guarantee removes nullability checks on cur->left/cur->right.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#