116. Populating Next Right Pointers in Each Node

Quick Identifier

• Topic: trees
• Pattern: BFS (or O(1) extra using next links)
• Difficulty: Medium
• Companies: Amazon, Microsoft, Bloomberg, Oracle, Google
• Frequency: High
• LeetCode: 116

Quick Sights

• Time Complexity: O(n) from the optimal approach.
• Space Complexity: O(1) from the optimal approach.
• Core Mechanism: You are given a perfect binary tree of Node values where each node has val, left, right, and next. Initially next is null. Populate each next to point to its immediate right neighbor on the same level; the rightmost node on each level points to null.

Concept Explanation

You are given a perfect binary tree of Node values where each node has val, left, right, and next. Initially next is null. Populate each next to point to its immediate right neighbor on the same level; the rightmost node on each level points to null.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• "Next pointer" on same level
• Perfect tree often enables O(1) extra by reusing already-filled next to reach the next node on the level above
• BFS with queue is the straightforward O(n) extra queue space approach

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• BFS — O(n) time / O(n) queue space — process level by level, link each node to the next in the queue order.
• Optimal (space) — O(n) time / O(1) auxiliary — treat each level as a linked list: follow next on parents to wire children.

Optimal Solution

Go

package main

type Node struct {
	Val   int
	Left  *Node
	Right *Node
	Next  *Node
}

func connect(root *Node) *Node {
	if root == nil {
		return nil
	}
	leftmost := root
	for leftmost.Left != nil {
		head := leftmost
		for head != nil {
			head.Left.Next = head.Right
			if head.Next != nil {
				head.Right.Next = head.Next.Left
			}
			head = head.Next
		}
		leftmost = leftmost.Left
	}
	return root
}

JavaScript

class Node {
	constructor(val = 0, left = null, right = null, next = null) {
		this.val = val;
		this.left = left;
		this.right = right;
		this.next = next;
	}
}

function connect(root) {
	if (root === null) {
		return null;
	}
	let leftmost = root;
	while (leftmost.left !== null) {
		let head = leftmost;
		while (head !== null) {
			head.left.next = head.right;
			if (head.next !== null) {
				head.right.next = head.next.left;
			}
			head = head.next;
		}
		leftmost = leftmost.left;
	}
	return root;
}

Walkthrough

Perfect tree levels 1–2–4. Start leftmost = root.

Invariant: at depth d, all next on depth < d are correct, so walking head = head.Next visits parents left-to-right for wiring depth d.

Edge Cases

• Single-node tree → no children loop runs zero times
• Guaranteed perfect tree in statement — algorithm relies on Left existing until leaves

Pitfalls

• Confusing this with problem 117 (not perfect) — that variant often needs queue or more elaborate linking
• Missing head.Right.Next = head.Next.Left when head.Next exists

Similar Problems

• 102. Binary Tree Level Order Traversal — explicit levels without pointer wiring.
• 199. Binary Tree Right Side View — right-edge visibility on levels.
• 236. Lowest Common Ancestor of a Binary Tree — different pointer reasoning on trees.

Variants

• Arbitrary binary tree next pointers (117) — typically queue-based or dummy-head level iterator.

Mind-Map Tags

#trees #bfs #next-pointer #perfect-tree #o1-space-trick