LeetCode 117 - Populating Next Right Pointers in Each Node II

The problem asks us to populate the next pointer for every node in a binary tree so that it points to the node immediately to its right on the same level. If no such node exists, the next pointer should remain NULL.

leetcodemediumlinked-listtreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 117

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

Solution

Problem Understanding

The problem asks us to populate the next pointer for every node in a binary tree so that it points to the node immediately to its right on the same level. If no such node exists, the next pointer should remain NULL.

Unlike the easier version of this problem, where the tree is guaranteed to be a perfect binary tree, this version allows any binary tree structure. Nodes may be missing children, levels may be incomplete, and the shape of the tree can be irregular. This makes the problem more challenging because we cannot rely on assumptions such as every parent having two children or every level being completely filled.

The input is the root node of a binary tree where each node has four fields:

val   -> node value
left  -> pointer to left child
right -> pointer to right child
next  -> pointer to the next right node

Initially, every next pointer is already NULL. Our job is to update these pointers in place.

The expected output is the same tree structure, but with all next pointers properly connected level by level. The actual tree structure does not change, only the next references.

The constraints tell us that the tree contains at most 6000 nodes. This size is small enough that a breadth first traversal using a queue would work efficiently. However, the follow up requirement explicitly asks for constant extra space, meaning we should avoid allocating additional memory proportional to the number of nodes. Recursive stack space does not count toward the extra space limit.

Several edge cases are important to recognize before designing a solution. The tree may be empty (root = []), in which case we simply return None. A level may contain only one node, meaning its next pointer should remain NULL. Nodes may have only one child, either left or right, which means our traversal logic must not assume both children exist. Finally, levels may be sparse and disconnected structurally, so naive sibling linking logic can fail.

Approaches

Brute Force Approach, Level Order Traversal Using a Queue

The most straightforward solution is to perform a breadth first search (BFS) using a queue.

We process the tree one level at a time. For each level, we keep track of all nodes currently in the queue. As we iterate through them, we connect each node's next pointer to the following node in that same level. The final node of the level gets NULL.

While processing a node, we enqueue its left and right children if they exist. Since BFS naturally visits nodes level by level, it guarantees correct horizontal connections.

This approach is correct because every level is processed independently and in left to right order. However, the drawback is space usage. In the worst case, the queue may contain an entire level of the tree, which can require O(n) extra memory.

Optimal Approach, Level Traversal Using Existing next Pointers

The key observation is that once we connect nodes in one level, we can reuse those next pointers to traverse that level without needing a queue.

Instead of storing nodes externally, we process one level at a time while building the next level's linked structure.

We maintain:

  • A pointer to the current level
  • A dummy node to build connections for the next level
  • A tail pointer that appends children into the next level chain

As we iterate through the current level using next pointers, we connect every child node encountered into a linked list for the next level. Once the current level is finished, we move to the next level by following dummy.next.

This works because every level becomes a temporary linked list, allowing us to move horizontally without extra memory.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) BFS with a queue, simple but violates constant space follow up
Optimal O(n) O(1) Uses already established next pointers to traverse levels

Algorithm Walkthrough

Optimal Algorithm

  1. Handle the empty tree case by immediately returning None if root is None. There is nothing to connect.
  2. Initialize a pointer called current_level to root. This pointer represents the leftmost node of the current level being processed.
  3. Start a loop that continues while current_level is not None. Each iteration processes exactly one tree level.
  4. Create a dummy node and a tail pointer. The dummy node acts as the temporary head of the linked list for the next level. The tail pointer tracks the most recently connected node.
  5. Traverse the current level using the already established next pointers. Begin with current = current_level.
  6. For every node in the current level:
  • If the node has a left child, connect it to tail.next, then move tail forward.
  • If the node has a right child, connect it similarly and move tail forward.
  1. Move horizontally across the current level using:
current = current.next

This avoids needing a queue. 8. After finishing the level, the dummy node contains the head of the next level through dummy.next. 9. Update:

current_level = dummy.next

This moves processing down one level. 10. Continue until no more levels remain. 11. Return the original root, since all connections were made in place.

Why it works

The key invariant is that before processing a level, all nodes in that level are already connected by next pointers. While traversing this level, we build the next level's linked structure from left to right. Because children are encountered in natural left to right order, the generated next chain is correct. Once the level is complete, we move down and repeat the process. Since every node is visited exactly once and linked correctly, the final tree satisfies the problem requirements.

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: 'Node') -> 'Node':
        if not root:
            return root

        current_level = root

        while current_level:
            dummy = Node(0)
            tail = dummy
            current = current_level

            while current:
                if current.left:
                    tail.next = current.left
                    tail = tail.next

                if current.right:
                    tail.next = current.right
                    tail = tail.next

                current = current.next

            current_level = dummy.next

        return root

The implementation begins by handling the empty tree case. If the root is None, we return immediately.

The current_level pointer tracks the first node of the level currently being processed. Inside the outer loop, we create a temporary dummy node and initialize tail to point at it. This pair is used to construct the linked list for the next level.

The inner loop traverses the current level using current.next. For every node, we append any existing children to the next level chain. The tail pointer ensures that connections happen in correct left to right order.

After processing the entire level, dummy.next points to the leftmost node of the next level, allowing the algorithm to continue downward.

Since all modifications happen in place and we never allocate memory proportional to tree size, the implementation satisfies the constant extra space requirement.

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 root
	}

	currentLevel := root

	for currentLevel != nil {
		dummy := &Node{}
		tail := dummy
		current := currentLevel

		for current != nil {
			if current.Left != nil {
				tail.Next = current.Left
				tail = tail.Next
			}

			if current.Right != nil {
				tail.Next = current.Right
				tail = tail.Next
			}

			current = current.Next
		}

		currentLevel = dummy.Next
	}

	return root
}

The Go implementation closely mirrors the Python solution. Since Go uses pointers explicitly, child access requires nil checks before linking nodes. The dummy node is created using &Node{}.

One language specific difference is pointer handling. In Python, objects are reference based automatically, while in Go we explicitly manipulate *Node pointers. Otherwise, the logic remains identical.

Worked Examples

Example 1

Input:

root = [1,2,3,4,5,null,7]

Tree:

        1
      /   \
     2     3
    / \     \
   4   5     7

Level 0

Variable Value
current_level 1
dummy.next None

Process node 1:

  • Connect 2
  • Connect 3

Resulting next chain:

2 -> 3 -> NULL

Move to next level:

current_level = 2

Level 1

Current chain:

2 -> 3

Process node 2:

  • Connect 4
  • Connect 5

Temporary chain:

4 -> 5

Process node 3:

  • No left child
  • Connect 7

Updated chain:

4 -> 5 -> 7 -> NULL

Move to next level:

current_level = 4

Level 2

Current chain:

4 -> 5 -> 7

No children exist.

Traversal ends.

Final connections:

1 -> NULL
2 -> 3 -> NULL
4 -> 5 -> 7 -> NULL

Output:

[1,#,2,3,#,4,5,7,#]

Example 2

Input:

root = []

Since the root is None, the function immediately returns None.

Output:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once
Space O(1) Only a few pointers are used, independent of tree size

The time complexity is O(n) because each node is processed exactly once while traversing levels. The inner traversal across levels collectively visits every node one time.

The space complexity is O(1) because we only maintain a few pointers such as current_level, current, dummy, and tail. No queue or recursion proportional to input size is used.

Test Cases

class Node:
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

def collect_levels(root):
    result = []
    level_start = root

    while level_start:
        current = level_start
        level = []
        next_level = None

        while current:
            level.append(current.val)

            if not next_level:
                next_level = current.left or current.right

            current = current.next

        result.append(level)
        level_start = next_level

    return result

solution = Solution()

# Example 1
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(7)

connected = solution.connect(root)
assert collect_levels(connected) == [[1], [2, 3], [4, 5, 7]]  # official example

# Example 2
assert solution.connect(None) is None  # empty tree

# Single node
root = Node(1)
connected = solution.connect(root)
assert connected.next is None  # single node should remain NULL

# Left-skewed tree
root = Node(1)
root.left = Node(2)
root.left.left = Node(3)

connected = solution.connect(root)
assert collect_levels(connected) == [[1], [2], [3]]  # one node per level

# Right-skewed tree
root = Node(1)
root.right = Node(2)
root.right.right = Node(3)

connected = solution.connect(root)
assert collect_levels(connected) == [[1], [2], [3]]  # only right children

# Sparse tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.right = Node(5)
root.right.right = Node(7)

connected = solution.connect(root)
assert root.left.next == root.right  # sibling connection
assert root.left.right.next == root.right.right  # cross-parent connection

# Full binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

connected = solution.connect(root)
assert collect_levels(connected) == [[1], [2, 3], [4, 5, 6, 7]]  # balanced tree
Test Why
Empty tree Validates null input handling
Single node Ensures isolated node keeps next = NULL
Example 1 Verifies official irregular tree case
Left skewed tree Tests missing right children
Right skewed tree Tests missing left children
Sparse tree Verifies cross parent linking
Full binary tree Ensures standard level linking works

Edge Cases

Empty Tree

An empty tree is the simplest edge case. A careless implementation may attempt to access attributes on None, causing runtime errors. The solution handles this immediately with an early return:

if not root:
    return root

This guarantees safety before any traversal begins.

Sparse Levels With Missing Children

A common source of bugs is assuming both left and right children exist. In this problem, nodes may have only one child or none at all. For example:

    1
   / \
  2   3
   \   \
    5   7

The algorithm checks child existence individually and appends whichever children are present. This ensures 5 correctly connects to 7, even though they come from different parents.

Single Node Per Level

In skewed trees, every level may contain only one node:

1
 \
  2
   \
    3

A naive BFS implementation may still work, but pointer based solutions sometimes incorrectly assume sibling connections exist. Here, the dummy node mechanism naturally handles this case because each level simply generates a linked list with one node whose next remains NULL.

Last Node in Each Level

The final node of every level must always point to NULL. A bug prone implementation might accidentally leave stale pointers behind. Since the algorithm only explicitly connects nodes forward and never assigns a successor to the final node, the last node naturally retains its default NULL value.