Log inSign up
mediumleetcodeNot Started

Populating Next Right Pointers in Each Node II

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

Trees
Solve on leetcode
Lesson

Problem Statement

Given a binary tree (which may not be a perfect tree): 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.

You must solve it using constant extra space O(1).

Example 1 · Example 1: Tree with Gaps:

Input: root = [1, 2, 3, 4, 5, null, 7] Tree: 1 / \ 2 3 / \ \ 4 5 7
Output: [1, #, 2, 3, #, 4, 5, 7, #]
Explanation: 4 -> 5 -> 7 -> NULL. Node 3 has no left child, but 5 connects directly to 7.

Example 2 · Example 2: Empty Tree:

Input: root = []
Output: []
Explanation: Returns null.

Constraints:

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

What You'll Learn

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

  • Handle sparse and asymmetric tree levels with the dummy head pattern.
  • Achieve strict O(1) space on general binary trees without queues.
  • Understand why simple pointer lookups fail when children are missing.

Pattern Recognition Trigger

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

Signals to Look For:

  • Populate next pointers on non-perfect binary tree.
  • Missing children and asymmetric levels.
  • Strict O(1) space requirement.

Algorithmic Decision Tree:

  • dummy = new Node(0); tail = dummy.
  • while curr: if curr.left: tail.next = curr.left, tail = tail.next; if curr.right: tail.next = curr.right, tail = tail.next; curr = curr.next.
  • curr = dummy.next.

Connected Patterns:

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

1. BFS Queue Level Order Traversal

Intuition

Push root to queue. For each level of size S, pop node and wire node.next to queue.front() for all except last element.

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: Pop node; if i < sz - 1: node.next = q.front().
  4. Step 4: Push non-null children.
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 level width w.

2. Recursive DFS (Right First)

Intuition

When searching for next neighbor in an arbitrary tree, right-side next pointers must already exist. Thus, recurse on right subtree BEFORE left subtree.

When to apply: Recursive solution.

Algorithm

  1. Step 1: If root == null return null.
  2. Step 2: Helper findNext(node): loops node.next looking for first non-null child.
  3. Step 3: Connect children using findNext(root.next).
  4. Step 4: connect(root.right); connect(root.left). Return root.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 Node* getNext(Node* node) {
9 while (node) {
10 if (node->left) return node->left;
11 if (node->right) return node->right;
12 node = node->next;
13 }
14 return nullptr;
15 }
16public:
17 Node* connect(Node* root) {
18 if (!root) return nullptr;
19 if (root->left) {
20 if (root->right) root->left->next = root->right;
21 else root->left->next = getNext(root->next);
22 }
23 if (root->right) {
24 root->right->next = getNext(root->next);
25 }
26 connect(root->right);
27 connect(root->left);
28 return root;
29 }
30};
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

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

3. Dummy Head Child Linked List (Strict O(1) Space)

Intuition

Use a dummy head node. For each level, iterate across parent nodes via curr = curr.next. Append curr.left and curr.right to tail. Advance curr = dummy.next to jump to next level.

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

Algorithm

  1. Step 1: Set cur = root.
  2. Step 2: While cur != null:
  3. Step 3: dummy = new Node(0); tail = dummy.
  4. Step 4: While cur != null: if cur.left: tail.next = cur.left; tail = tail.next; if cur.right: tail.next = cur.right; tail = tail.next; cur = cur.next.
  5. Step 5: cur = dummy.next (start of next level). Return root.

Dummy Head Next Pointer Trace for [1, 2, 3, 4, 5, null, 7]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Process root 1
Visual state
Values and pointers at this exact step
tree
Root
1
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 = 3
Decision / next transition
Move to row 2 -> 3.
Why this step matters

Step 1: Process root 1. Dummy collects left (2) and right (3). 2.next = 3. Advance to next level: curr = 2.

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 Node* cur = root;
11 while (cur) {
12 Node dummy(0);
13 Node* tail = &dummy;
14 while (cur) {
15 if (cur->left) { tail->next = cur->left; tail = tail->next; }
16 if (cur->right) { tail->next = cur->right; tail = tail->next; }
17 cur = cur->next;
18 }
19 cur = dummy.next;
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) — Every node processed once in linear time.
  • Space complexity: O(1) — Strictly O(1) auxiliary space with zero recursion stack and zero queue.

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 level.Queue memory.
2.Recursive DFS (Right First)O(n)O(h)Recurse right first to ensure right-side next pointers exist.Recursive call stack.
3.Dummy Head Child Linked ListOptimalO(n)O(1)Dummy head stitches child level into linked list; jump to dummy.next.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root is null -> returns null.
  • Skewed tree (single child chains): correctly links only valid nodes.
  • Wide gaps between siblings: dummy head stitches across gap seamlessly.

Interview Tips & Best Practices

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

  1. Show how the dummy head eliminates complex if-else logic for finding the first non-null child of the next level.
  2. Emphasize that this works for ANY binary tree, whereas Problem I requires a perfect tree.

Quick Comprehension Check

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

1.Why is the dummy head pattern so effective for non-perfect binary trees compared to direct pointer calculations?

Back to DSA Sheet