Populating Next Right Pointers in Each Node

LeetCode 116 | Difficulty: Medium

Medium

Problem Description

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:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

- The number of nodes in the tree is in the range `[0, 2^12 - 1]`.

- `-1000 <= Node.val <= 1000`

Follow-up:

- You may only use constant extra space.

- The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

Topics: Linked List, Tree, Depth-First Search, Breadth-First Search, Binary Tree

---

Approach

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

Tree BFS (Level-Order)

Use a queue to process the tree level by level. At each level, process all nodes in the queue, then add their children. Track the level size to know when one level ends and the next begins.

When to use

Level-order traversal, level-based aggregation, right/left side view.

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: Java (Best: 0 ms)

Metric	Value
Runtime	0 ms
Memory	N/A
Date	2018-07-13

Solution

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        compute(root);
    }
    
    private void compute(TreeLinkNode current)
    {
        if(current==null || current.left == null) return;
        current.left.next = current.right;
        if(current.next!=null)
        {
            current.right.next = current.next.left;
        }
        compute(current.left);
        compute(current.right);
    }
}

Solution 2: C++ (Best: 17 ms)

Metric	Value
Runtime	17 ms
Memory	N/A
Date	2018-05-20

Solution

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root == NULL) return;
    TreeLinkNode *pre = root;
    TreeLinkNode *cur = NULL;
    while(pre->left) {
        cur = pre;
        while(cur) {
            cur->left->next = cur->right;
            if(cur->next) cur->right->next = cur->next->left;
            cur = cur->next;
        }
        pre = pre->left;
    }
    }
};

📜 1 more C++ submission(s)

Submission (2018-05-20) — 20 ms, N/A

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root == NULL) return;
    TreeLinkNode *pre = root;
    TreeLinkNode *cur = NULL;
    while(pre->left) {
        cur = pre;
        while(cur) {
            cur->left->next = cur->right;
            if(cur->next) cur->right->next = cur->next->left;
            cur = cur->next;
        }
        pre = pre->left;
    }
    }
};

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.