Domain 2MediumCORE

Populating Next Right Pointers in Each Node

We are given the root of a perfect binary tree, meaning every internal node has exactly two children and all leaves reside at the same depth level. The goal is to populate each next pointer so that it points to its immediate right neighbor on the same level, or NULL if none exists (e.g., for the last node in a row).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Tree#Depth-first Search#Breadth-first Search

116. Populating Next Right Pointers in Each Node

Model: qwen3.5:9b
Topics: Tree,Depth-first Search,Breadth-first Search
FAANG asked: 1
Acceptance rate: 49.6%


Problem Breakdown

We are given the root of a perfect binary tree, meaning every internal node has exactly two children and all leaves reside at the same depth level. The goal is to populate each next pointer so that it points to its immediate right neighbor on the same level, or NULL if none exists (e.g., for the last node in a row).

Inputs: A root node of a binary tree defined by val, left, right. Outputs: The modified tree where all next pointers are populated. Constraints & Edge Cases:

  • Perfect Binary Tree Property: This is critical. It guarantees that if we have two nodes at the same level, their children exist in a predictable pattern (siblings). If it were an arbitrary binary tree, this problem would be significantly harder without parent pointers or extra space for tracking levels.
  • Empty Input: root could be None. The code must handle this immediately to avoid dereferencing nulls.
  • Single Node: A leaf node has no children; the loop conditions should naturally terminate here.
  • Memory Constraint (Follow-up): We are restricted to O(1)O(1) extra space excluding recursion stack depth if recursive, or strictly heap memory for iterative solutions. This rules out a standard BFS queue approach which would require storing nodes in a list/queue proportional to the tree width (O(N)O(N)).

Intuition

Initially, one might think of using Breadth-First Search (BFS) with a deque or list. We process level by level, connecting children. However, this requires O(W)O(W) space where WW is the maximum width of the tree at any depth. For deep trees like perfect binary trees (N=4096  ⟹  W≈2048N=4096 \implies W \approx 2048), this violates the constant extra space follow-up constraint.

The key insight comes from observing that we are allowed to use the next pointers themselves for traversal after they have been set up in previous iterations.

  1. Sibling Connection: For any node, its left child’s next pointer should always point to its right sibling (its own right child). This is trivial: node.left.next = node.right.
  2. Cross-Level Connection: If a parent has a next neighbor (parent.next != None), the current level’s last node connects across levels? No, we need to connect children of adjacent parents at the same depth in the next iteration. Specifically: The right child of Node A should point to the left child of Node B (where B is A.next).
  3. Traversal Strategy: We can iterate through a level using the existing next pointers established by previous levels. Since it’s a perfect tree, we don’t need parent pointers; just knowing that if I am at node A and have children, then my sibling exists to connect across (unless I’m on the rightmost edge).

This allows us to traverse horizontally without allocating new nodes for a queue. We essentially “walk” down the levels using the next links we built in previous steps. This reduces space complexity from O(N)O(N) to O(1)O(1).

Approach

We will use an iterative approach that processes level by level, but instead of storing all nodes at current depth (BFS), we traverse them sequentially using their newly established next pointers.

Algorithm:

  1. Initialization: Start with a pointer (head) pointing to the root node. This represents the leftmost node of the current level being processed as parents for children in the next level.
  2. Outer Loop (Level Traversal): Continue while there are nodes at the current depth that have children (i.e., head.left is not None). Since it’s a perfect tree, if we reach leaves (head.left == None), we stop because no more levels need connecting.
  3. Inner Loop (Sibling Connection): Inside each level iteration:
    • Initialize a pointer (curr) to the current node in this level traversal chain.
    • While curr.next exists:
      • Connect siblings: Set curr.left.next = curr.right.
      • Connect across parents: If curr.next is not None, set curr.right.next = curr.next.left. This links the right child of one parent to the left child of its neighbor.
    • Move horizontally using the newly created link: Update curr = curr.next.
  4. Move Down: After finishing a level traversal (all nodes at current depth processed), move down one level by setting head to head.left. This prepares us for connecting children in the next deeper level.

This logic ensures every node’s pointers are set exactly once, and we never allocate extra memory beyond variables holding references.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of nodes. We visit each node at most twice (once as a parent in outer loop context or inner traversal). Specifically, every internal node’s children are connected once per level pass. Since we traverse down to leaves exactly once for connections, it scales linearly with input size.
  • Space Complexity: O(1)O(1) extra space. We only use pointers (head, curr) which take constant memory regardless of tree depth or width (excluding the recursion stack if recursive were used).

Solution

"""
# 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 not root or (not root.left and not root.right):
            return root
        
        leftmost = root

        while leftmost.left:
            curr = leftmost

            while curr: 
                curr.left.next = curr.right
                if curr.next:
                    curr.right.next = curr.next.left
                curr = curr.next
            leftmost = leftmost.left
        return root

Edge Cases Handled

  • Empty Tree (root is None): The initial check if not root... returns immediately. No pointers are accessed on nulls.
  • Single Node: Loop condition while head.left evaluates to False (since single node has no left child), function exits early, which is correct as there are no next neighbors needed for a leaf-only tree.
  • Perfect Binary Tree Structure: The logic relies on the guarantee that if we have children at level LL, they exist in pairs. If it were not perfect, curr.next.left might be null when expected; however, constraints specify “perfect binary tree,” so this assumption holds valid for all internal nodes processed by the inner loop.
  • Large Input (N<4096N < 4096): The iterative approach avoids recursion depth limits (stack overflow) and memory overhead of queues, making it robust even near integer stack limits in languages like C++ or Java, though Python handles deep stacks well here anyway.