Problem Description

You are given a binary tree where each node has the following structure:

• val: an integer value
• left: pointer to the left child
• right: pointer to the right child
• next: pointer that initially points to NULL

Your task is to populate each next pointer so that it points to the node's next right neighbor on the same level. If there is no next right node on the same level, the next pointer should remain NULL.

For example, if you have a binary tree like:

       1
      / \
     2   3
    / \   \
   4   5   7

After connecting the next pointers, the connections would be:

• Node 1's next → NULL (no node to its right on the same level)
• Node 2's next → Node 3 (same level, to the right)
• Node 3's next → NULL (no node to its right on the same level)
• Node 4's next → Node 5 (same level, to the right)
• Node 5's next → Node 7 (same level, to the right)
• Node 7's next → NULL (no node to its right on the same level)

The solution uses a level-order traversal (BFS) approach with a queue. For each level of the tree, it processes all nodes from left to right, connecting each node's next pointer to the subsequent node in the queue at that level. The algorithm maintains a pointer p to track the previous node processed at the current level, allowing it to set p.next = node for each new node encountered. This ensures all nodes at the same level are connected via their next pointers.

Flowchart Walkthrough

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

Is it a graph?

• Yes: A binary tree is a special type of graph with nodes (tree nodes) and edges (parent-child relationships). Each node can have connections to other nodes through left, right, and next pointers.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where each node has left and right children.

DFS

• Yes: We arrive at DFS as a potential solution approach for this tree problem.

Conclusion: The flowchart suggests using a DFS (Depth-First Search) approach for connecting the next right pointers in the binary tree.

While the provided solution uses BFS (level-order traversal), DFS is equally valid for this problem. A DFS approach would involve:

1. Traversing the tree depth-first while keeping track of the level
2. Maintaining a list or map of the rightmost node seen at each level
3. As we visit each node, connecting it to the previously seen node at the same level
4. This can be implemented using either recursive DFS or iterative DFS with a stack

The tree structure naturally lends itself to DFS traversal patterns, making it a suitable choice according to the flowchart's decision path.

Intuition

The key insight for this problem is recognizing that we need to connect nodes that are at the same level but not necessarily siblings. When we think about tree traversal, we naturally process nodes level by level or depth by depth.

The most straightforward way to connect nodes on the same level is to process them in the order they appear from left to right. This immediately suggests a level-order traversal pattern. If we can visit all nodes at level 1, then all nodes at level 2, and so on, we can easily link them together as we encounter them.

Think of it like people standing in rows for a group photo - we want each person to hold hands with the person to their right in the same row. The natural way to do this is to go row by row (level by level) and have each person extend their hand to the next person we encounter in that row.

When using BFS with a queue, we have a beautiful property: at any point during the traversal, the queue contains all nodes at the current level (and only those nodes) before we start processing them. This means we can:

1. Know exactly how many nodes are at the current level (len(q))
2. Process them one by one from left to right
3. Connect each node to the next one in the queue at that level

The pattern emerges: as we dequeue each node, we can set the previous node's next pointer to point to the current node. By maintaining a p pointer that tracks the "previous" node at the current level, we create a chain of connections across each level. When we finish a level, we reset p to None for the next level.

This approach naturally handles all cases - complete trees, incomplete trees, and even skewed trees - because we're simply connecting whatever nodes exist at each level in their left-to-right order.

Solution Approach

The solution implements a level-order traversal using BFS (Breadth-First Search) with a queue data structure. Here's how the algorithm works:

1. Initialize the Queue

• Start by checking if the root is None. If it is, return immediately.
• Create a queue using deque([root]) and add the root node to begin the traversal.

2. Process Each Level

• The outer while q: loop continues as long as there are nodes to process.
• At the start of each level, we capture the current queue size with len(q). This tells us exactly how many nodes are at the current level.
• Initialize a pointer p = None to track the previous node at this level.

3. Connect Nodes Within Each Level

• The inner for _ in range(len(q)): loop processes exactly the number of nodes at the current level.
• For each node:
  • Dequeue it with node = q.popleft()
  • If p exists (not the first node in this level), set p.next = node to create the connection
  • Update p = node to make the current node the "previous" for the next iteration
  • Add the node's children to the queue for the next level: first node.left, then node.right (if they exist)

4. Level Completion

• After processing all nodes at a level, the last node's next automatically remains NULL (its initial value).
• The algorithm moves to the next level with a fresh p = None.

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. In the worst case (a complete binary tree), the last level could contain up to n/2 nodes, making it O(n).

The beauty of this approach is that the queue naturally maintains the left-to-right order of nodes at each level, and by processing exactly len(q) nodes at a time, we ensure we only connect nodes within the same level.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider this binary tree:

     1
    / \
   2   3
  /     \
 4       5

Initial State:

• All next pointers are NULL
• Queue: [1]

Level 1 Processing (1 node):

• len(q) = 1, so we'll process 1 node
• p = None (start of level)
• Dequeue node 1:
  • Since p = None, we don't set any next pointer
  • Update p = node 1
  • Add children: Queue becomes [2, 3]
• Result: Node 1's next remains NULL

Level 2 Processing (2 nodes):

• len(q) = 2, so we'll process 2 nodes
• p = None (start of new level)
• Iteration 1 - Dequeue node 2:
  • Since p = None, we don't set any next pointer
  • Update p = node 2
  • Add children: Queue becomes [3, 4]
• Iteration 2 - Dequeue node 3:
  • Since p = node 2, set node 2.next = node 3 ✓
  • Update p = node 3
  • Add children: Queue becomes [4, 5]
• Result: Node 2 → Node 3, Node 3's next remains NULL

Level 3 Processing (2 nodes):

• len(q) = 2, so we'll process 2 nodes
• p = None (start of new level)
• Iteration 1 - Dequeue node 4:
  • Since p = None, we don't set any next pointer
  • Update p = node 4
  • No children to add
• Iteration 2 - Dequeue node 5:
  • Since p = node 4, set node 4.next = node 5 ✓
  • Update p = node 5
  • No children to add
• Result: Node 4 → Node 5, Node 5's next remains NULL

Final connections:

• Level 1: 1 → NULL
• Level 2: 2 → 3 → NULL
• Level 3: 4 → 5 → NULL

The key insight is that by processing exactly len(q) nodes at each level and maintaining the previous node pointer p, we naturally create the left-to-right connections within each level while keeping levels separate.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses BFS (Breadth-First Search) to traverse the binary tree level by level. Each node in the tree is visited exactly once - it's added to the queue once and processed once when it's dequeued. For each node, we perform constant time operations: dequeuing, setting the next pointer, and enqueuing its children. Since we visit all n nodes exactly once and perform O(1) operations for each node, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the maximum size of the queue q during execution. In the worst case, the queue needs to store all nodes at the widest level of the tree. For a complete binary tree, the maximum width occurs at the last level, which can contain up to n/2 nodes (approximately half of all nodes in a complete binary tree are at the last level). Therefore, the space complexity is O(n/2) = O(n). Additionally, we use a constant amount of extra space for variables like p and node, but this doesn't affect the overall space complexity.

Common Pitfalls

1. Not Maintaining Level Boundaries

One of the most common mistakes is failing to properly track where one level ends and the next begins. Without capturing level_size = len(queue) at the start of each level, you might accidentally connect nodes from different levels.

Incorrect approach:

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

Solution: Always capture the queue size before processing each level and iterate exactly that many times.

2. Forgetting to Reset the Previous Pointer

Another pitfall is not resetting the previous_node pointer to None at the start of each new level. This could cause the last node of one level to incorrectly point to the first node of the next level.

Incorrect approach:

# WRONG: previous_node not reset between levels
previous_node = None
while queue:
    level_size = len(queue)
    # Missing: previous_node = None here!
    for _ in range(level_size):
        current_node = queue.popleft()
        if previous_node:
            previous_node.next = current_node
        previous_node = current_node
        # ... add children

Solution: Initialize previous_node = None inside the outer while loop, right after determining the level size.

3. Using the Wrong Queue Operations

Using pop() instead of popleft() would process nodes in LIFO order rather than FIFO, breaking the left-to-right traversal requirement.

Incorrect approach:

# WRONG: Using pop() gives LIFO behavior
current_node = queue.pop()  # This gets the last element!

Solution: Always use popleft() for BFS to maintain FIFO order and ensure left-to-right processing.

4. Modifying Queue Size During Level Processing

Some might try to optimize by checking while queue and level_size > 0: but if you're not careful with the counter, you might process nodes from multiple levels together.

Solution: Use a simple for _ in range(level_size): loop which guarantees exactly level_size iterations, making the logic cleaner and less error-prone.