Log inSign up
mediumleetcodeNot Started

Populating Next Right Pointers in Each Node

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node { int val; Node *left; Node *right; Node *next; };

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.

Example 1 · Example 1: Perfect Tree of 7 Nodes:

Input: root = [1, 2, 3, 4, 5, 6, 7] Tree: 1 / \ 2 3 / \ / \ 4 5 6 7
Output: [1, #, 2, 3, #, 4, 5, 6, 7, #]
Explanation: 1->NULL; 2->3->NULL; 4->5->6->7->NULL.

Example 2 · Example 2: Empty Tree:

Input: root = []
Output: []
Explanation: Empty tree remains empty.

Constraints:

  • The number of nodes in the tree is in the range [0, 212 - 1].
  • -1000 <= Node.val <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Leverage existing linked list pointers to navigate tree levels.
  • Achieve strict O(1) auxiliary memory without queues.
  • Distinguish between intra-parent and inter-parent sibling connections.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Perfect binary tree.
  • Populate next right pointers.
  • O(1) extra memory constraint.

Algorithmic Decision Tree:

  • curr.left.next = curr.right.
  • if curr.next != null -> curr.right.next = curr.next.left.
  • Advance curr = curr.next; when row ends, leftmost = leftmost.left.

Connected Patterns:

Populating Next Right Pointers in Each Node IIBinary Tree Level Order TraversalFlatten Binary Tree to Linked List

1. Standard BFS Queue Level Order Traversal

Intuition

Level order traversal with queue. For each level of size S, pop node; if i < S - 1, node.next = queue.front().

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If root == null return null.
  2. Step 2: Queue q with root.
  3. Step 3: For level size S: pop node; if i < S - 1: node.next = q.front().
  4. Step 4: Push children to queue.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 Node* connect(Node* root) {
10 if (!root) return nullptr;
11 queue<Node*> q;
12 q.push(root);
13 while (!q.empty()) {
14 int sz = q.size();
15 for (int i = 0; i < sz; ++i) {
16 Node* cur = q.front(); q.pop();
17 if (i < sz - 1) cur->next = q.front();
18 if (cur->left) q.push(cur->left);
19 if (cur->right) q.push(cur->right);
20 }
21 }
22 return root;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once.
  • Space complexity: O(w) — Queue holds maximum level width w <= n/2 nodes.

2. Recursive Preorder DFS Connections

Intuition

Base case: if root == null or root.left == null return. Connect root.left.next = root.right. If root.next != null, connect root.right.next = root.next.left. Recurse left and right.

When to apply: Clean recursive approach.

Algorithm

  1. Step 1: If root == null || root.left == null return root.
  2. Step 2: root.left.next = root.right.
  3. Step 3: If root.next != null: root.right.next = root.next.left.
  4. Step 4: connect(root.left); connect(root.right). Return root.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 Node* connect(Node* root) {
10 if (!root || !root->left) return root;
11 root->left->next = root->right;
12 if (root->next) root->right->next = root->next->left;
13 connect(root->left);
14 connect(root->right);
15 return root;
16 }
17};
18
19int main() {
20 // Sample driver execution
21 cout << "Execution completed successfully." << endl;
22 return 0;
23}
24

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once.
  • Space complexity: O(h) — Recursion call stack takes O(h) space.

3. Iterative Level Linked-List Walk (Strict O(1) Space)

Intuition

Keep leftmost pointer. While leftmost.left != null: traverse across current level via curr = curr.next. Connect curr.left.next = curr.right. If curr.next != null: curr.right.next = curr.next.left. At end of row, leftmost = leftmost.left.

When to apply: Optimal gold-standard solution for strict O(1) auxiliary space.

Algorithm

  1. Step 1: If root == null return null.
  2. Step 2: leftmost = root.
  3. Step 3: While leftmost.left != null: cur = leftmost; while cur != null: cur.left.next = cur.right; if cur.next: cur.right.next = cur.next.left; cur = cur.next; leftmost = leftmost.left.
  4. Step 4: Return root.

O(1) Next Pointer Trace for root = [1, 2, 3, 4, 5, 6, 7]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Start at level 0 (node 1)
Visual state
Values and pointers at this exact step
tree
Root
1 (next: null)
L
2 (next: 3)
R
3 (next: null)

Node order shown; add connections to display explicit tree edges.

2 -> 3: 2
Check / comparison
2.next set to 3
Decision / next transition
Advance to next level (node 2).
Why this step matters

Step 1: Start at level 0 (node 1). Link left child 2 to right child 3: 2.next = 3. Next pointer established.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 Node* connect(Node* root) {
10 if (!root) return nullptr;
11 Node* leftmost = root;
12 while (leftmost->left) {
13 Node* cur = leftmost;
14 while (cur) {
15 cur->left->next = cur->right;
16 if (cur->next) cur->right->next = cur->next->left;
17 cur = cur->next;
18 }
19 leftmost = leftmost->left;
20 }
21 return root;
22 }
23};
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n) — Visits each node once in linear time.
  • Space complexity: O(1) — Strictly O(1) auxiliary space; no queue, no recursion stack.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.BFS QueueO(n)O(w)Queue holds current level; wire next to q.front().Queue memory.
2.Recursive Preorder DFSO(n)O(h)Wire children and recurse.Call stack.
3.Iterative Level Linked-List WalkOptimalO(n)O(1)Use upper level next pointers to walk and wire lower level.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root is null -> returns null.
  • Single node: leaves next as null -> returns root.
  • Rightmost nodes at each level: next pointer correctly remains null.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the follow-up requirement: 'You may only use constant extra space. Recursive approach is fine, implicit stack space does not count.'
  2. Show how the iterative level-linked list approach achieves literal O(1) space with no stack at all.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can we connect cross-parent siblings via curr.right.next = curr.next.left without maintaining a queue?

Back to DSA Sheet