Problem Statement

Populating Next Right Pointers

You are given a perfect binary tree. A binary tree is a structure where each node has at most two children, a left child and a right child. "Perfect" means every parent has exactly two children and all the leaves (the bottom nodes with no children) sit on the same level, so the tree fills in completely like a pyramid. Each node also has a third pointer called next. Your job is to set every node's next pointer so it points to the node directly to its right on the same level. If a node is the rightmost one on its level, its next stays NULL (meaning "nothing there"). Picture each level of the tree as a row of kids holding hands left to right, and next is the hand reaching to the neighbor on the right. The simple way to do this is BFS (breadth-first search), which means visiting the tree one level at a time using a queue, a waiting line where you add to the back and take from the front. That works but the queue can hold a whole level of nodes, so it uses O(n) extra space. The trick here is that once we connect one level, those next pointers act as a ready-made path across that level, so we can walk the level without a queue and use O(1) space, meaning a fixed small amount no matter how big the tree is.

mediumTreeBFSTreesTime: O(n) · Space: O(1)

Signals to notice

connect each node to next right neighboruse existing next pointersO(1) space level traversal

Brute force first

BFS with queue, connect within each level — O(n) space for queue.

The key insight

Traverse current level via next pointers (already set). Connect children level: left.next = right, right.next = parent.next.left. O(n) time, O(1) space.

Trace it on `root=[1,2,3,4,5,6,7] (perfect binary tree)`

init: leftmost=1; outer loop checks leftmost.left=2 exists -> enter
level0 curr=1: set 2.next=3 (left.next=right); curr.next=NULL so no cross-link; curr=NULL -> level done. Result: 2->3->NULL
drop down: leftmost=leftmost.left=2; leftmost.left=4 exists -> enter
level1 curr=2: 4.next=5; curr.next=3 so 5.next=3.left=6; curr=3
level1 curr=3: 6.next=7; curr.next=NULL so no cross-link; curr=NULL -> level done. Result: 4->5->6->7->NULL
drop down: leftmost=leftmost.left=4; leftmost.left=NULL -> exit outer loop
return root: every node's next set, rightmost of each level -> NULL

What must stay true

The current level's next pointers enable horizontal traversal without a queue. While traversing, connect the next level's children using the parent's next pointer.

Shape of the loop

leftmost = root
while leftmost.left exists:        # one iteration per level
    curr = leftmost
    while curr:                    # walk level via existing next ptrs
        curr.left.next = curr.right                 # link siblings
        if curr.next: curr.right.next = curr.next.left   # bridge parents
        curr = curr.next
    leftmost = leftmost.left       # descend to next level
return root

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not connecting across parents — node.right.next should be node.next.left, bridging children of adjacent parents.

Trees Pattern