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:
rootcould beNone. 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 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 ().
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 space where is the maximum width of the tree at any depth. For deep trees like perfect binary trees (), 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.
- 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. - Cross-Level Connection: If a parent has a
nextneighbor (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 isA.next). - Traversal Strategy: We can iterate through a level using the existing
nextpointers 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 to .
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:
- 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. - Outer Loop (Level Traversal): Continue while there are nodes at the current depth that have children (i.e.,
head.leftis not None). Since it’s a perfect tree, if we reach leaves (head.left == None), we stop because no more levels need connecting. - Inner Loop (Sibling Connection): Inside each level iteration:
- Initialize a pointer (
curr) to the current node in this level traversal chain. - While
curr.nextexists:- Connect siblings: Set
curr.left.next = curr.right. - Connect across parents: If
curr.nextis not None, setcurr.right.next = curr.next.left. This links the right child of one parent to the left child of its neighbor.
- Connect siblings: Set
- Move horizontally using the newly created link: Update
curr = curr.next.
- Initialize a pointer (
- Move Down: After finishing a level traversal (all nodes at current depth processed), move down one level by setting
headtohead.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: where 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: 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 (
rootis None): The initial checkif not root...returns immediately. No pointers are accessed on nulls. - Single Node: Loop condition
while head.leftevaluates 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 , they exist in pairs. If it were not perfect,
curr.next.leftmight 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 (): 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.