Populate next pointer to right node in Binary Tree

Problem

Given a binary tree

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

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Examples

Example 1:

Input:
          1
        /  \
       2    3
     /    /  \
    4    6    7

Output:
          1 --------> NULL
        /  \
       2 -> 3 ------> NULL
     /    /  \
    4 -> 6 -> 7 ----> NULL

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Solution

Method 1 - Using Recursion

The recursive solution is built around the idea that:

1. The next pointer of a node can be established using its immediate children and the parent's next pointer.
2. If a node has:
   • A left child, its next pointer should point to the right child of the same node (if exists).
   • A right child or left child (when right is not available) can use the parent's next pointer to find the next available sibling or cousin at the same level.
3. The recursion is performed in a top-down manner, ensuring that the children of the current node are connected before moving deeper down the tree.

Approach

The recursive approach works in the following steps:

1. Base Case: If the node is None, return immediately.
2. Recursive Case:
   • Connect the left child's next pointer to the right child (if it exists).
   • Use a helper function (findNext) to "scan" the parent's next pointer until it finds the first non-None sibling with children for connecting the current node's children.
   • Recurse first on the right subtree and then on the left subtree:
     • Right subtree is updated first because a node's next pointer (used in findNext) must already be set when connecting the left subtree.

Code

Java

public class Solution {
    public Node connect(Node root) {
        if (root == null) return null;

        // Connect left child
        if (root.left != null) {
            root.left.next = (root.right != null) ? root.right : findNext(root);
        }

        // Connect right child
        if (root.right != null) {
            root.right.next = findNext(root);
        }

        // Recursive calls, right first to ensure child "next" pointers are set
        connect(root.right);
        connect(root.left);

        return root;
    }

    private Node findNext(Node root) {
        while (root.next != null) { // Traverse parent level using next pointers
            root = root.next; // Move to the next parent node
            if (root.left != null) return root.left; // First left child found
            if (root.right != null) return root.right; // First right child found
        }
        return null; // No valid child found
    }
}

Python

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

class Solution:
    def connect(self, root: Node) -> Node:
        if not root:
            return None  # Base case: If root is None, return
        
        # Connect left child's next pointer
        if root.left:
            if root.right:  # Connect to right child if exists
                root.left.next = root.right
            else:  # Otherwise, use findNext
                root.left.next = self.findNext(root)
        
        # Connect right child's next pointer
        if root.right:
            root.right.next = self.findNext(root)
        
        # Recursively connect peers: right subtree first, then left subtree
        self.connect(root.right)
        self.connect(root.left)
        
        return root

    def findNext(self, root: Node) -> Node:
        # Find the next node with children on the same level
        while root.next:
            root = root.next
            if root.left:  # Return the left child if exists
                return root.left
            if root.right:  # Return the right child if exists
                return root.right
        return None  # No valid next node found

Method 2 - BFS

The main idea is:

1. Use a queue to perform level-order traversal (Breadth-First Search).
2. For every level:
   • Iterate over all nodes in that level.
   • Connect the next pointer of each node to its neighbour (the next node in the queue).
   • If the node is the last in the level, its next pointer is set to null.
3. Add children of the current node to the queue and repeat for the next level.

Code

Java

  public class Solution {
    static class Node {
        int val;
        Node left, right, next;

        Node(int x) {
            val = x;
            left = right = next = null;
        }
    }

    public Node connect(Node root) {
        if (root == null) return null;

        // Queue for level-order traversal
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size(); // Number of nodes at the current level
            Node prev = null;

            for (int i = 0; i < size; i++) {
                Node node = queue.poll();

                // Connect current node's next pointer to the previous node
                if (prev != null) {
                    prev.next = node;
                }
                prev = node;

                // Add children to the queue
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }

            // Last node in the level points to null
            prev.next = null;
        }

        return root;
    }
}

Python

class Solution:
    def connect(self, root: Node) -> Node:
        if not root:
            return None
        
        # Queue for level-order traversal
        queue = deque([root])
        
        while queue:
            size = len(queue)  # Number of nodes at the current level
            prev = None
            
            for _ in range(size):
                node = queue.popleft()
                
                # Connect current node's next pointer to the previous node
                if prev:
                    prev.next = node
                prev = node
                
                # Add children to the queue
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            # Last node in the level points to None
            prev.next = None
        
        return root

Complexity

• ⏰ Time complexity: O(n). Each node is visited exactly once during the traversal.
• 🧺 Space complexity: O(n). In the worst case (a binary tree that is "wide" at the bottom level), the queue stores up to the entire width of a level.