Problem Description

You are given a perfect binary tree where all leaves are at the same level and every parent node has exactly two children. Each node in the tree has the following structure:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Your task is to populate each next pointer to point to its next right node on the same level. If there is no next right node (i.e., the node is the rightmost node on that level), the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

For example, if you have a perfect binary tree:

        1
       / \
      2   3
     / \ / \
    4  5 6  7

After connecting the next pointers, it should look like:

        1 -> NULL
       / \
      2->3 -> NULL
     / \ / \
    4->5->6->7 -> NULL

The connections are made horizontally across each level, linking nodes from left to right. The rightmost node at each level points to NULL.

The solution uses a Breadth-First Search (BFS) approach with a queue to traverse the tree level by level. For each level, it processes all nodes from left to right, connecting each node to the next node in the queue at the same level. The algorithm maintains a pointer p to track the previous node and sets p.next to the current node, effectively creating the horizontal connections.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a binary tree, which is a special type of graph with nodes (tree nodes) and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a perfect binary tree where each node has connections to its children.

DFS

• Yes: We arrive at DFS as our algorithm choice for tree problems.

Conclusion: The flowchart suggests using a Depth-First Search (DFS) approach for this tree problem.

Why DFS Works Here

While the provided solution uses BFS (level-order traversal), DFS is equally valid and can solve this problem efficiently. With DFS, we can:

1. Recursive approach: Process the tree depth-first while maintaining references to connect nodes at the same level
2. Use parent pointers: Since it's a perfect binary tree, we can leverage the parent's next pointer to connect children nodes
3. Space efficiency: DFS can achieve O(1) extra space (excluding recursion stack) compared to BFS's O(w) where w is the width of the tree

A DFS solution would traverse down the tree, and at each level:

• Connect the left child to the right child
• If the parent has a next pointer, connect the parent's right child to the parent's next node's left child
• Recursively process both subtrees

This demonstrates that tree problems often have multiple valid approaches, and the flowchart correctly identifies DFS as a suitable pattern for tree-based problems.

Intuition

The key insight for this problem comes from understanding what we're trying to achieve: we need to connect nodes horizontally across each level of the tree, essentially creating "linked lists" at each depth.

Think about how you would manually connect these nodes if you were drawing the tree on paper. You'd naturally process the tree level by level, connecting each node to its right neighbor. This immediately suggests a level-order traversal pattern.

Why does BFS naturally fit here? When we use a queue for BFS, at any given moment, the queue contains all nodes at the current level. This is perfect because:

1. We can process all nodes at the same level together
2. We know exactly how many nodes are at each level (the queue size at the start of processing that level)
3. We can connect them sequentially as we dequeue them

The elegant part of the solution is the use of a temporary pointer p that tracks the "previous" node we just processed. As we dequeue each node:

• If p exists (not the first node in the level), we set p.next to the current node
• We update p to point to the current node
• We add the node's children to the queue for the next level

This creates a chain: node1 -> node2 -> node3 -> ... -> NULL for each level.

While DFS could also solve this (by using the parent's next pointer to find cousins), BFS is more intuitive here because the problem is fundamentally about connecting nodes at the same level - and BFS naturally groups nodes by level. It's like reading the tree line by line, left to right, which matches exactly what we need to do.

Solution Approach

The solution implements a Breadth-First Search (BFS) using a queue to traverse the tree level by level. Here's how the implementation works:

1. Base Case Check:

if root is None:
    return root

If the tree is empty, we simply return None.

2. Initialize the Queue:

q = deque([root])

We start with a queue containing only the root node. The deque (double-ended queue) provides efficient O(1) operations for both adding and removing elements.

3. Level-by-Level Processing:

while q:
    p = None
    for _ in range(len(q)):

The outer while loop continues as long as there are nodes to process. For each level, we:

• Initialize p to None - this will track the previous node in the current level
• Use range(len(q)) to process exactly the number of nodes at the current level

4. Connecting Nodes:

node = q.popleft()
if p:
    p.next = node
p = node

For each node in the current level:

• We dequeue it from the left of the queue
• If p is not None (meaning this isn't the first node in the level), we connect the previous node to the current node via p.next = node
• We update p to point to the current node for the next iteration

5. Adding Children for Next Level:

if node.left:
    q.append(node.left)
if node.right:
    q.append(node.right)

We add the children of the current node to the queue. These will be processed in the next level iteration.

Key Pattern: The algorithm ensures that when we start processing a level, the queue contains exactly all nodes of that level and nothing else. As we process these nodes, we're simultaneously:

• Connecting them horizontally (via the next pointers)
• Preparing the next level (by adding their children to the queue)

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(w) where w is the maximum width of the tree. For a perfect binary tree, this is O(n/2) = O(n) for the last level.

Example Walkthrough

Let's walk through a small perfect binary tree to see how the BFS solution connects the nodes:

Initial tree:
      1
     / \
    2   3

Step 1: Initialize

• Queue: [1]
• Start processing level 1

Step 2: Process Level 1 (root)

• Queue size = 1, so we'll process 1 node
• Dequeue node 1, p = None
• Since p is None, we don't set any next pointer
• Update p = 1
• Add children: Queue becomes [2, 3]
• Level 1 complete: Node 1.next remains NULL

Step 3: Process Level 2

• Queue size = 2, so we'll process 2 nodes
• Initialize p = None for this level

First node of level 2:

• Dequeue node 2, current p = None
• Since p is None, we don't set any next pointer
• Update p = 2
• No children to add (leaf node)

Second node of level 2:

• Dequeue node 3, current p = 2
• Since p is not None, set p.next = 3 (so 2.next = 3)
• Update p = 3
• No children to add (leaf node)

Step 4: Complete

• Queue is empty, algorithm terminates

Final Result:

      1 -> NULL
     / \
    2->3 -> NULL

The key insight: At each level, the first node doesn't get a next pointer set (since p starts as None), but every subsequent node gets connected to by the previous node. The rightmost node naturally points to NULL since no node sets its next pointer.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of nodes in the binary tree. This is because the algorithm uses a breadth-first search (BFS) approach with a queue, visiting each node exactly once. Each node is enqueued once and dequeued once, and the operations performed on each node (setting the next pointer, checking children) take constant time O(1).

The space complexity is O(n), where n is the number of nodes in the binary tree. The space is dominated by the queue q used for BFS traversal. In the worst case, the queue needs to store all nodes at the maximum width level of the tree. For a complete binary tree, the last level can contain up to n/2 nodes, making the space complexity O(n). Additionally, the variable p only uses O(1) extra space, which doesn't affect the overall space complexity.

Common Pitfalls

1. Not Preserving Level Boundaries

A frequent mistake is failing to process nodes strictly level by level, which results in incorrect connections between nodes from different levels.

Incorrect Implementation:

# WRONG: This connects nodes across levels
while queue:
    node = queue.popleft()
    if queue:  # This might connect to a node from the next level!
        node.next = queue[0]
    if node.left:
        queue.append(node.left)
    if node.right:
        queue.append(node.right)

Why it fails: When processing the last node of a level, the queue already contains nodes from the next level. Setting node.next = queue[0] would incorrectly connect a node to its child or nephew instead of NULL.

Correct Approach:

while queue:
    level_size = len(queue)  # Capture current level size
    for i in range(level_size):  # Process exactly this many nodes
        node = queue.popleft()
        # Only connect if not the last node in the level
        if i < level_size - 1:
            node.next = queue[0]  # Safe: queue[0] is in same level
        # Add children for next level
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

2. Inefficient Space Usage for Perfect Binary Trees

Since the problem guarantees a perfect binary tree, you can optimize space by using the already-established next pointers instead of a queue.

Space-Optimized Solution (O(1) space):

def connect(self, root: Optional['Node']) -> Optional['Node']:
    if not root:
        return root
  
    # Start with root level
    leftmost = root
  
    # Process each level using the next pointers from previous level
    while leftmost.left:  # While there's a next level
        # Iterate through current level using next pointers
        head = leftmost
        while head:
            # Connect left child to right child
            head.left.next = head.right
          
            # Connect right child to next node's left child
            if head.next:
                head.right.next = head.next.left
          
            # Move to next node in current level
            head = head.next
      
        # Move to next level
        leftmost = leftmost.left
  
    return root

3. Forgetting to Handle Edge Cases

While the BFS solution naturally handles most edge cases, developers sometimes forget to check for an empty tree or make assumptions about tree structure.

Common Oversight:

# WRONG: Assumes tree is never empty
def connect(self, root):
    queue = deque([root])  # Will process None if root is None!
    while queue:
        # Processing None will cause AttributeError
        node = queue.popleft()
        # ...

Proper Handling:

def connect(self, root):
    if not root:  # Always check for empty tree
        return root
    queue = deque([root])
    # ... rest of the logic

4. Misunderstanding the Problem Requirements

Some developers mistakenly try to connect nodes vertically (parent to child) or diagonally instead of horizontally within the same level.

Remember: The next pointer should only connect nodes that are:

• On the same level (same distance from root)
• Adjacent in left-to-right order
• The rightmost node of each level should have next = NULL