116. Populating Next Right Pointers in Each Node

At a Glance

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

Problem (one-liner)

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.

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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