#117

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Populating Next Right Pointers in Each Node II

Populate each next pointer in a binary tree to its immediate right node, handling nulls and uneven levels efficiently using pointer manipulation.

linked list tree depth first search breadth first search binary tree

Problem Statement

Given a binary tree where each node has left and right child pointers and an additional next pointer initially set to NULL, populate each next pointer to point to the node immediately to its right at the same level. If there is no such node, the next pointer should remain NULL. The tree can be uneven and contain null children, which requires careful pointer handling.

You must update the next pointers in place without creating extra nodes. The algorithm should traverse the tree efficiently, connecting each node at the current level before moving to the next, and must handle cases where children are missing while preserving proper connections across levels.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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

Example 2

Input: root = [1,2,3,4,5,null,7]

Output: [1,#,2,3,#,4,5,7,#]

Given the above 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 3

Input: root = []

Output: []

Example details omitted.

Constraints

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

Solution Approach

Level-Order Traversal Using a Queue

Perform a breadth-first search by using a queue to iterate through each level of the tree. For every level, link nodes from left to right using the queue order, and ensure that the last node's next pointer is set to NULL. This approach handles null children naturally but uses additional space proportional to the maximum width of the tree, which is the queue size. It's straightforward and prevents missing cross-level connections.

Iterative Pointer Manipulation Without Extra Space

Use pointers to traverse each level without a queue by maintaining a current pointer for the node being processed and a dummy head to track the start of the next level. Connect child nodes as you traverse the current level, and move down level by level. This method achieves O(1) space usage while ensuring that all nodes, including those in uneven structures, have correctly populated next pointers. Careful management of next and child pointers is critical to avoid losing references.

Recursive Depth-First Traversal

Apply a recursive approach that connects nodes by traversing right before left to ensure that next pointers are available when connecting the left child. Each recursive call handles a node's children and establishes links to the next right node found in the same level. This leverages the call stack for traversal and simplifies pointer connections but may use O(h) space for the recursion stack, where h is the tree height. Proper handling of null children avoids incorrect next connections.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the traversal approach, with BFS and iterative pointer methods requiring O(n) to visit each node once. Space complexity varies: the BFS queue method can use up to O(w) space for the maximum width, the iterative pointer method uses O(1) extra space, and recursion uses O(h) stack space. These match the provided approach-dependent time and space complexity constraints.

What Interviewers Usually Probe

Do you see how missing children affect the next pointer connections across levels?
Can you implement this without using extra memory while still connecting all nodes correctly?
Will you traverse the tree level by level or rely on recursion to handle next pointer assignments?

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle the end of a level, leaving the last node's next pointer incorrectly pointing to a non-null value.
Assuming the tree is perfect and not handling missing children, which breaks cross-level connections.
Using recursion in the wrong order (left before right), causing next pointers to reference null instead of the correct neighbor.

Follow-up variants

Populating Next Right Pointers in Each Node (perfect binary tree version) with O(1) space requirements.
Level Order Traversal of Binary Tree with pointers returned as linked lists per level.
Flatten Binary Tree to Linked List in-place, connecting nodes in pre-order with similar pointer manipulations.

FAQ

How do I handle null children when populating next pointers?

Skip null children while traversing each level and ensure that the next pointer of the previous non-null node points to the next available node, or NULL if none exist.

Can I solve this problem using O(1) space?

Yes, by using iterative pointer manipulation with a dummy head to track the start of each level, you can update next pointers without extra memory beyond a few pointers.

Why is the BFS queue approach sometimes less optimal?

It requires additional space proportional to the maximum width of the tree, which can be significant for large or unbalanced trees, unlike the iterative pointer method.

Does recursion order matter when connecting next pointers?

Yes, processing the right child before the left ensures that left children can correctly reference the next right node already connected, avoiding null misassignments.

What pattern does Populating Next Right Pointers in Each Node II primarily teach?

It emphasizes linked-list pointer manipulation in trees, showing how careful traversal and connection logic handles uneven levels and missing children efficiently.

terminal

Solution

Solution 1: BFS

We use a queue $q$ for level order traversal. Each time we traverse a level, we connect the nodes of the current level in order.

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""


class Solution:
    def connect(self, root: "Node") -> "Node":
        if root is None:
            return root
        q = deque([root])
        while q:
            p = None
            for _ in range(len(q)):
                node = q.popleft()
                if p:
                    p.next = node
                p = node
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return root

Solution 2: Space Optimization

The space complexity of Solution 1 is relatively high because it requires a queue to store the nodes of each level. We can implement it with constant space.

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""


class Solution:
    def connect(self, root: "Node") -> "Node":
        if root is None:
            return root
        q = deque([root])
        while q:
            p = None
            for _ in range(len(q)):
                node = q.popleft()
                if p:
                    p.next = node
                p = node
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return root

Continue Practicing

#116 populating next right pointers in each node #114 flatten binary tree to linked list #112 path sum