Populating Next Right Pointers in Each Node
Populating Next Right Pointers in Each Node is a medium trees & bst problem solved with the traversals pattern.
The best approach, optimal (walk each level through next pointers), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs with a queue) up.
Problem
You are given a perfect binary tree: every internal node has exactly two children and all leaves sit on the same depth. Each node has the fields val, left, right and an extra pointer next, which starts out as null.
Fill in every next pointer so it points to the node immediately to its right on the same level. The last node of each level keeps next = null. Return the root.
Examples
Example 1
- Input
root = [10, 20, 30, 40, 50, 60, 70]- Output
[10, #, 20, 30, #, 40, 50, 60, 70, #]- Why
- Each level is read left to right through the next pointers; # marks the end of a level, where next is null.
Example 2
- Input
root = [5]- Output
[5, #]- Why
- A single node has no right neighbour, so its next stays null.
Example 3
- Input
root = []- Output
[]- Why
- An empty tree has nothing to connect.
Constraints
- The tree has
0to2^12 - 1nodes. - The tree is perfect: every internal node has two children and all leaves are on the same level.
-1000 <= Node.val <= 1000- Follow-up: use only
O(1)extra space (the recursion stack does not count).
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (BFS with a queue) | O(n) | O(n) |
| Optimal (walk each level through next pointers) | O(n) | O(1) |
1Brute force (BFS with a queue)
O(n)Every node is enqueued and dequeued once.O(n)The queue holds a whole level, and the last level of a perfect tree has about n / 2 nodes.Traverse level by level with a queue. Within a level, every node points to the node that comes out of the queue right after it; the last node of the level keeps null.
- If root is null, return it.
- Push root into a queue.
- While the queue is not empty: let size be the current queue size (one level).
- Pop size nodes; for each one except the last, set next to the queue's front. Push each node's children.
- Return root.
class Solution {
public Node connect(Node root) {
if (root == null) return null;
Queue<Node> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Node node = q.poll();
if (i < size - 1) node.next = q.peek();
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
}
return root;
}
}class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if root is None:
return None
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i < size - 1:
node.next = q[0]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return rootclass Solution {
public:
Node* connect(Node* root) {
if (!root) return nullptr;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Node* node = q.front();
q.pop();
if (i < size - 1) node->next = q.front();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return root;
}
};function connect(root) {
if (root === null) return null;
let level = [root];
while (level.length > 0) {
const next = [];
for (let i = 0; i < level.length; i++) {
const node = level[i];
if (i < level.length - 1) node.next = level[i + 1];
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
level = next;
}
return root;
}2Optimal (walk each level through next pointers)
O(n)Each node is visited once as `cur` while its children are linked.O(1)Only two pointers; the next links themselves are the output.The level you are standing on is already linked, so it behaves like a linked list. Walk it with next and wire up the level below: a node's left child points to its right child, and its right child points to the left child of the node's next neighbour. Then drop down to the leftmost node of the next level.
- leftmost = root.
- While leftmost is not null and has a left child (the level below exists):
- Walk cur = leftmost, cur = cur.next: set cur.left.next = cur.right; if cur.next != null, set cur.right.next = cur.next.left.
- Move down: leftmost = leftmost.left.
- Return root.
class Solution {
public Node connect(Node root) {
Node leftmost = root;
while (leftmost != null && leftmost.left != null) {
for (Node cur = leftmost; cur != null; cur = cur.next) {
cur.left.next = cur.right;
if (cur.next != null) {
cur.right.next = cur.next.left;
}
}
leftmost = leftmost.left;
}
return root;
}
}class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
leftmost = root
while leftmost is not None and leftmost.left is not None:
cur = leftmost
while cur is not None:
cur.left.next = cur.right
if cur.next is not None:
cur.right.next = cur.next.left
cur = cur.next
leftmost = leftmost.left
return rootclass Solution {
public:
Node* connect(Node* root) {
Node* leftmost = root;
while (leftmost && leftmost->left) {
for (Node* cur = leftmost; cur; cur = cur->next) {
cur->left->next = cur->right;
if (cur->next) {
cur->right->next = cur->next->left;
}
}
leftmost = leftmost->left;
}
return root;
}
};function connect(root) {
let leftmost = root;
while (leftmost !== null && leftmost.left !== null) {
for (let cur = leftmost; cur !== null; cur = cur.next) {
cur.left.next = cur.right;
if (cur.next !== null) {
cur.right.next = cur.next.left;
}
}
leftmost = leftmost.left;
}
return root;
}Edge cases to test
- Empty tree
- A single node
- The rightmost node of every level must keep next = null
- Linking across subtrees: a left subtree's rightmost node points to the right subtree's leftmost node
Hints
Hint 1
A level-order traversal visits each level left to right, so linking each node to the one dequeued after it (on the same level) works.
Hint 2
Once a level is linked, you can walk it like a linked list using next.
Hint 3
While walking level L, set the children's pointers: node.left.next = node.right, and node.right.next = node.next.left when node.next exists.
FAQ
What is the best time complexity for Populating Next Right Pointers in Each Node?
Optimal (walk each level through next pointers) runs in O(n) time and O(1) extra space. Each node is visited once as `cur` while its children are linked.
Which pattern does Populating Next Right Pointers in Each Node use?
It is a trees & bst problem that uses the traversals pattern. Other problems with the same pattern: Binary Tree Level Order Traversal, Binary Tree Zigzag Level Order Traversal, Binary Tree Level Order Traversal II.
Is there a brute force solution for Populating Next Right Pointers in Each Node?
Yes. Brute force (BFS with a queue) takes O(n) time and O(n) space. Traverse level by level with a queue.
Which edge cases should I test for Populating Next Right Pointers in Each Node?
Empty tree; A single node; The rightmost node of every level must keep next = null; Linking across subtrees: a left subtree's rightmost node points to the right subtree's leftmost node.