LeetCode 116 - Populating Next Right Pointers in Each Node

Difficulty: 🟡 Medium
Topics: Linked List, Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to populate the next pointers of nodes in a perfect binary tree. A perfect binary tree has all levels completely filled; every internal node has exactly two children, and all leaves are at the same depth. The next pointer of a node should point to the node immediately to its right on the same level. If there is no node to the right (the node is the last on its level), the next pointer should be NULL.

The input is the root of a binary tree where each node has four fields: val (the integer value), left (pointer to the left child), right (pointer to the right child), and next (initially NULL). The output is the same tree, but with the next pointers correctly set.

Constraints indicate that the tree size is up to 2^12 - 1 nodes, which is modest enough for an O(n) solution. Since it is a perfect binary tree, we can safely assume every internal node has two children. This simplifies traversal logic because we do not have to check for missing children.

Edge cases include an empty tree (root is NULL) and a tree with only one node. In both cases, the next pointers remain NULL.

The follow-up constraint asks us to achieve constant extra space, meaning we cannot use a queue for level order traversal unless we count the implicit recursion stack as acceptable space.

Approaches

The brute-force approach is to perform a level-order traversal using a queue. At each level, we iterate through all nodes, linking each node to the next node in the queue. After finishing a level, we set the next pointer of the last node to NULL. While this works correctly and is easy to implement, it requires O(n) additional space for the queue, which violates the constant space follow-up.

The optimal solution exploits the properties of a perfect binary tree. For each node, its left child’s next should point to its right child. Additionally, the node’s right child’s next should point to the left child of the node’s next (if it exists). This allows us to link all nodes in a level using only previously established next pointers without extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Uses a queue for level-order traversal; links nodes per level
Optimal	O(n)	O(1)	Exploits perfect binary tree properties; no extra data structures needed

Algorithm Walkthrough

Handle the base case: If the root is NULL, return NULL.
Initialize a pointer to traverse levels: Set leftmost to the root. This pointer will always point to the first node of the current level.
Iterate level by level: While leftmost.left is not NULL, do the following:
Initialize a head pointer to traverse nodes within the current level.
For each node in this level, connect its children:
head.left.next = head.right to connect the left child to the right child.
If head.next exists, head.right.next = head.next.left to connect the right child to the next subtree’s left child.
Move head to head.next to continue linking nodes in the current level.
Move to the next level: Set leftmost to leftmost.left.
Return the root.

Why it works: The invariant is that at the start of each level, all next pointers of the previous level are correctly set. Using this invariant, we can link the current level without any extra data structure.

Python 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:
            return None
        
        leftmost = root
        
        while leftmost.left:
            head = leftmost
            while head:
                # Connect left -> right
                head.left.next = head.right
                # Connect right -> next.left if available
                if head.next:
                    head.right.next = head.next.left
                head = head.next
            leftmost = leftmost.left
        
        return root

The code starts by checking if the tree is empty. Then it uses leftmost to track the first node of each level. Within each level, head iterates over nodes and connects children using the established next pointers. After finishing a level, it moves down one level via leftmost.left. The loop terminates when there are no more child nodes.

Go Solution

/**
 * Definition for a Node.
 * 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
}

In Go, we handle nil in place of NULL. The logic is identical to the Python version, using two pointers to iterate levels and link nodes efficiently.

Worked Examples

Example 1: Input [1,2,3,4,5,6,7]

Level	head	Links Created
1	1	1.next = NULL
2	2	2.next = 3, 3.next = NULL
3	4	4.next = 5, 5.next = 6, 6.next = 7, 7.next = NULL

The root's left and right children are connected. Then, the right child’s next points to the next subtree’s left child. This continues until all levels are connected.

Example 2: Input []

Output: []. The code returns None immediately.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once to set its `next` pointers
Space	O(1)	No additional data structures are used; only a few pointers are maintained

The optimal approach leverages the perfect binary tree structure, avoiding any extra memory beyond a couple of pointers.

Test Cases

# test cases
root = None
assert Solution().connect(root) is None  # empty tree

node1 = Node(1)
assert Solution().connect(node1) == node1  # single node tree

# Perfect binary tree of 3 levels
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node7 = Node(7)
node2 = Node(2, node4, node5)
node3 = Node(3, node6, node7)
root = Node(1, node2, node3)
res = Solution().connect(root)
assert res.next is None
assert node2.next == node3
assert node3.next is None
assert node4.next == node5
assert node5.next == node6
assert node6.next == node7
assert node7.next is None

Test	Why
Empty tree	Validates base case handling
Single node	Ensures no invalid next pointer assignment
Three-level perfect tree	Tests full linking across multiple levels

Edge Cases

The first important edge case is an empty tree, where root is NULL. A naive implementation might try to access root.left and cause a runtime error. The solution immediately returns NULL to handle this safely.

The second edge case is a tree with a single node. Since there are no children, all next pointers remain NULL. The loop checking leftmost.left ensures it does not attempt unnecessary connections.

The third edge case is a deep perfect binary tree, where the number of levels approaches the maximum allowed by constraints. The solution must correctly traverse all levels without stack overflow. Since the algorithm uses an iterative approach, it handles large depths efficiently, only using a constant number of pointers.