#116

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Populating Next Right Pointers in Each Node

Connect each node across every level by reusing established next links to traverse a perfect binary tree without extra queue storage.

linked list tree depth first search breadth first search binary tree

Problem Statement

You are given the root of a perfect binary tree, meaning every internal node has exactly two children and all leaves appear on the same depth. Each node also has a next pointer that should point to the node immediately to its right on the same level. When a node is already the rightmost node of its level, its next pointer must remain NULL.

Your task is to fill these next pointers in place and return the root after the connections are created. The tree may be empty, and all next pointers start as NULL before processing begins. The important constraint is not just linking siblings under one parent, but also linking children across neighboring parents on the same level.

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,6,7]

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

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 3

Input: root = []

Output: []

Example details omitted.

Constraints

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

Solution Approach

Use each completed level as a linked list

The strongest approach for this problem walks one level while building the next. Start from the leftmost node of the current level. Since the tree is perfect, every node on that level has both left and right children. For each parent, connect parent.left.next to parent.right. Then, if parent.next exists, connect parent.right.next to parent.next.left. Move across the current level using the already available next chain. After finishing that level, drop to leftmost.left and repeat. This turns the tree into a sequence of linked horizontal passes without needing a queue.

Why the perfect-tree property changes the solution

This problem becomes much easier because you never need to guess whether a child exists or search for the next available neighbor. In an arbitrary binary tree, cross-parent links require scanning ahead for the next non-null child, which is a different and more error-prone problem. Here, each parent always contributes exactly two children, so every bridge is deterministic: left goes to right, and right goes to the next parent’s left. That certainty is the core trade-off that enables constant extra space and keeps the pointer logic compact.

Alternative BFS framing and when to mention it

A breadth-first traversal with a queue also works and is often the easiest first explanation in an interview. You process one level at a time, pop nodes in order, and connect each node’s next to the following node in that level. The weakness is extra memory proportional to the width of the tree, which misses the more elegant follow-up for this problem. It is still useful to mention BFS briefly as a baseline, then pivot to the in-place pointer method and explain that the next pointers themselves replace the queue once a level has been wired.

Complexity Analysis

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

The in-place level traversal runs in O(n) time because each node is visited a constant number of times while its child links are wired. The provided space complexity is O(1) extra space because the solution reuses existing next pointers and only stores a few traversal pointers. A queue-based BFS alternative is still O(n) time, but its space grows to O(w), where w is the maximum level width.

What Interviewers Usually Probe

Do you recognize that the perfect-tree structure lets you connect parent.right directly to parent.next.left without searching for a neighbor?
Can you explain why traversing a level through next pointers replaces a BFS queue after the previous level has been connected?
Will you distinguish between this perfect-tree problem and the harder version where missing children break the simple cross-parent link rule?

Common Pitfalls or Variants

Common pitfalls

Connecting only left.next = right and forgetting the cross-parent bridge right.next = parent.next.left, which leaves gaps between subtrees.
Using a generic BFS explanation only, then missing the constant-space follow-up that this perfect binary tree specifically allows.
Advancing to the next level incorrectly, such as moving with leftmost.next instead of leftmost.left, which breaks the vertical progression.

Follow-up variants

Populating Next Right Pointers in Each Node II, where the tree is not perfect and missing children force neighbor discovery.
Return the level-order traversal using next pointers after wiring, proving the horizontal links are correct without reusing the original tree edges.
Set previous-left pointers instead of next-right pointers, reversing the same level-linking idea and changing traversal direction.

FAQ

What is the key pattern in Populating Next Right Pointers in Each Node?

The core pattern is level-by-level pointer stitching. You treat one finished level as a linked list through next pointers, then use each parent to wire the entire level below it from left to right.

Why does the O(1) extra space solution work only because the tree is perfect?

Because every parent definitely has both left and right children, the next neighbor is always known. You never need to search ahead for an existing child, so the cross-parent connection rule stays fixed and local.

What exact links do I create for each parent node?

For every parent, first connect left child to right child. Then, if the parent has a next neighbor, connect the parent’s right child to that neighbor’s left child. Those two assignments build the next level completely.

Is BFS still acceptable for LeetCode 116?

Yes. BFS is a valid baseline and easier to describe initially, but it uses extra memory for the queue. Interviewers often expect you to notice that this problem’s perfect-tree constraint enables a cleaner constant-space pointer solution.

What is the most common failure mode in this linked-list pointer manipulation problem?

The usual mistake is solving only inside each parent and forgetting to bridge across parents. That produces correct sibling pairs like 4 to 5, but misses links like 5 to 6 between adjacent subtrees.

terminal

Solution

Solution 1: BFS

Use a queue for level order traversal, and each time you traverse a level, 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: "Optional[Node]") -> "Optional[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: DFS

Use recursion for preorder traversal, and each time you traverse to a node, connect its left and right child nodes 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: "Optional[Node]") -> "Optional[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

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