# Populating Next Right Pointers in Each Node
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/populating-next-right-pointers-in-each-node)
Canonical: https://scaleengineer.com/dsa/problems/populating-next-right-pointers-in-each-node
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Linked List, Tree, Binary Tree
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Google](https://scaleengineer.com/companies/google), [Oracle](https://scaleengineer.com/companies/oracle), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Snowflake](https://scaleengineer.com/companies/snowflake), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel)
---
## Problem
You are given a **perfect binary tree** where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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`.

**Example 1:**

![](https://assets.glich.co/dsa/populating-next-right-pointers-in-each-node/image0.png) 

**Input:** root = [1,2,3,4,5,6,7]
**Output:** [1,#,2,3,#,4,5,6,7,#]
**Explanation:** Given the above perfect 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.

**Example 2:**

**Input:** root = []
**Output:** []

**Constraints:**

* The number of nodes in the tree is in the range `[0, 212 - 1]`.
* `-1000 <= Node.val <= 1000`

**Follow-up:**

* You may only use constant extra space.
* The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

# Approaches
## Level Order Traversal (BFS) with a Queue
This approach uses a standard Breadth-First Search (BFS) or level order traversal. We traverse the tree level by level using a queue. For each level, we iterate through its nodes and connect each node to the one immediately following it in the queue, which corresponds to its right neighbor.
**Time:** O(N) · **Space:** O(N)
**Pros:** The logic is straightforward and easy to understand, as it's a direct application of level order traversal.; This approach is general and works for any binary tree, not just perfect ones (though the problem specifies a perfect binary tree).
**Cons:** This approach uses extra space for the queue. In the worst-case scenario (a complete, perfect binary tree), the maximum number of nodes at any level is `(N+1)/2`, where `N` is the total number of nodes. This leads to a space complexity of O(N), which does not satisfy the follow-up constraint of using only constant extra space.
### Explanation
The core idea is to process the tree one level at a time. We use a queue to store the nodes of the current level. Before processing a level, we record the number of nodes in it. Then, we dequeue nodes one by one. For each dequeued node, we set its `next` pointer to the node that is currently at the front of the queue, unless it's the last node of the level. While processing each node, we also enqueue its children for the next level. This ensures that we systematically connect all nodes at a given level before moving on to the next.

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

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

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();

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

                // If it's not the last node in the current level
                if (i < levelSize - 1) {
                    node.next = queue.peek();
                }

                // Add children for the next level
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return root;
    }
}
```
### Algorithm
1. Handle the edge case where the root is `null`. If so, return `null`.
2. Initialize a `Queue` data structure and add the `root` node to it.
3. Loop as long as the queue is not empty. In each iteration, the queue holds all nodes of a single level.
4. Determine the number of nodes at the current level by getting the `size()` of the queue.
5. Iterate from `i = 0` to `size - 1`. In each step:
    a. Dequeue a node, let's call it `current`.
    b. If this is not the last node of the level (i.e., `i < size - 1`), its `next` pointer should point to the next node in the level, which is currently at the front of the queue (`queue.peek()`).
    c. If the `current` node has a left child, enqueue it for the next level's processing.
    d. If the `current` node has a right child, enqueue it as well.
6. After the loops complete, all `next` pointers will be correctly populated. Return the `root`.

## Recursive Approach (Preorder Traversal)
A recursive approach can solve this problem by traversing the tree in a preorder fashion (Root, Left, Right). The function processes the current node by connecting its children, and then recursively calls itself for the left and right subtrees. The key is that connections at a level are made before descending to the next level.
**Time:** O(N) · **Space:** O(log N)
**Pros:** The code is elegant and concise.; It meets the problem's follow-up constraints, as the implicit recursion stack space is not counted as extra space.; The logic naturally follows the tree's structure.
**Cons:** While the problem statement allows for the recursion stack space, in a general context, this approach uses O(log N) space for a balanced tree, which is not strictly O(1).; For extremely deep trees, this could lead to a stack overflow error, although this is unlikely given the problem constraints.
### Explanation
The recursive solution relies on the fact that we can establish connections for the children of a node if we are at that node. A function `connect(root)` will perform the connections for the level below `root`.

First, we connect the direct children: `root.left.next = root.right`. This is straightforward.

Second, we need to connect nodes that do not share the same parent, for example, node 5 and node 6 in the example. This is done by connecting the right child of a node to the left child of its parent's `next` node. So, if `root.next` exists, we set `root.right.next = root.next.left`. This works because the `next` pointers for the current level are assumed to be already populated by the calls from the level above.

We must recurse on the left subtree before the right subtree. This ensures that when we are at `connect(root.right)`, the `root.next` pointers have been fully established across the entire level.

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

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

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

        // Connect the right child to the next subtree's left child
        if (root.right != null && root.next != null) {
            root.right.next = root.next.left;
        }

        // Recurse for left and right subtrees
        connect(root.left);
        connect(root.right);

        return root;
    }
}
```
### Algorithm
1. Define a recursive function, say `connect(root)`.
2. The base case for the recursion is when the `root` is `null` or it's a leaf node (`root.left` is `null`). In this case, simply return.
3. For the current `root` node, establish two types of connections:
    a. Connect the left child to the right child: `root.left.next = root.right`.
    b. If the `root` itself has a `next` pointer (meaning it's not the rightmost node of its level), connect its right child to the left child of its sibling: `root.right.next = root.next.left`.
4. Make two recursive calls. It's important to recurse on the left subtree first (`connect(root.left)`) and then the right subtree (`connect(root.right)`). This order ensures that the `next` pointers for a level are established from left to right, so when we process a node, its `next` pointer is already correctly set by its parent.

## Iterative Approach using Level Pointers (Constant Space)
This is the most optimal approach, achieving constant extra space. It avoids recursion and explicit queues by using the `next` pointers that have already been established at the previous level. We iterate through the tree level by level, using a pointer to the start of each level and another pointer to traverse it.
**Time:** O(N) · **Space:** O(1)
**Pros:** Extremely efficient in terms of space, using only a few pointers, thus achieving O(1) space complexity.; Satisfies the follow-up constraint without any special assumptions about stack space.; Avoids the overhead of recursion and potential for stack overflow.
**Cons:** The logic can be slightly more complex to visualize and implement compared to the straightforward BFS approach.
### Explanation
This iterative solution cleverly uses the structure of the problem. We can think of it as a level-order traversal without a queue. We maintain a pointer, `leftmost`, which is the first node of each level. The outer loop iterates through the levels of the tree, starting from the root.

For each level (starting at `leftmost`), we use another pointer, `head`, to traverse from left to right using the `next` pointers that were set up by the previous iteration of the outer loop. As we traverse with `head`, we establish the `next` pointers for the level *below*. 

There are two types of connections to make for each node `head`:
1.  The connection between its own children: `head.left.next = head.right`.
2.  The connection between its right child and the left child of its sibling: `head.right.next = head.next.left`. This is only possible if `head.next` is not null.

After traversing the entire level with `head`, we move down to the next level by setting `leftmost = leftmost.left` and repeat the process.

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

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

        // Start with the root of the tree. This will be the leftmost node of the first level.
        Node leftmost = root;

        // Loop as long as we are not on the last level (i.e., leftmost has children).
        while (leftmost.left != null) {
            // 'head' will traverse the current level.
            Node head = leftmost;

            // Inner loop to traverse the nodes of the current level.
            while (head != null) {
                // Connection 1: Connect left child to right child.
                head.left.next = head.right;

                // Connection 2: Connect right child to the next node's left child.
                if (head.next != null) {
                    head.right.next = head.next.left;
                }

                // Move to the next node in the current level.
                head = head.next;
            }
            
            // Move to the start of the next level.
            leftmost = leftmost.left;
        }

        return root;
    }
}
```
### Algorithm
1. If `root` is `null`, return `null`.
2. Initialize a pointer `leftmost` to the `root`. This pointer will always mark the beginning of the current level we are processing.
3. Start an outer loop that continues as long as `leftmost` has a left child (i.e., we are not at the last level).
4. Inside the outer loop, create a `head` pointer and initialize it to `leftmost`. This `head` pointer will traverse the current level from left to right.
5. Start an inner loop that continues as long as `head` is not `null`.
    a. Connect the children of the `head` node: `head.left.next = head.right`.
    b. Check if `head` has a `next` node. If it does, it means there's a node to its right on the same level. Connect `head`'s right child to its neighbor's left child: `head.right.next = head.next.left`.
    c. Move the `head` pointer to the next node in the current level: `head = head.next`.
6. After the inner loop completes, all nodes in the level below `leftmost` are connected. Move to the start of that next level by updating `leftmost = leftmost.left`.
7. Once the outer loop finishes, return the `root`.

# Solutions
### Java

```java
/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } }; */ class Solution { public Node connect ( Node root ) { if ( root == null ) { return root ; } Deque < Node > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { Node p = null ; for ( int n = q . size (); n > 0 ; -- n ) { Node node = q . poll (); if ( p != null ) { p . next = node ; } p = node ; if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } } return root ; } }
```

### CPP

```cpp
/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} }; */ class Solution { public: Node * connect ( Node * root ) { if ( ! root ) { return root ; } queue < Node *> q { { root } }; while ( ! q . empty ()) { Node * p = nullptr ; for ( int n = q . size (); n ; -- n ) { Node * node = q . front (); q . pop (); if ( p ) { p -> next = node ; } p = node ; if ( node -> left ) { q . push ( node -> left ); } if ( node -> right ) { q . push ( node -> right ); } } } return root ; } };
```

### Python

```python
""" # 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 """ ''' >>> d = deque((5,1,9,2)) >>> d.popleft() 5 >>> d.popleft() 1 >>> >>> >>> d = deque([5,1,9,2]) >>> d.popleft() 5 >>> d.popleft() 1 ''' from collections import deque class Solution : def connect ( self , root : "Optional[Node]" ) -> "Optional[Node]" : if root is None : return root # q = deque(root) ===> TypeError: 'Node' object is not iterable # make it a list [], so it's iterable q = deque ([ root ]) while q : prev = None for _ in range ( len ( q )): node = q . popleft () if prev : p . next = node prev = node if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) return root class Solution : def connect ( self , root : 'Node' ) -> 'Node' : if not root : return root l = [ root ] # list while l : size = len ( l ) for i in range ( size ): node = l . pop ( 0 ) # pop() is last, pop(0) is first of list if i < size - 1 : node . next = l [ 0 ] if node . left : l . append ( node . left ) if node . right : l . append ( node . right ) return root # recursion class Solution : def connect ( self , root : "Optional[Node]" ) -> "Optional[Node]" : self . _connect ( root , None ) return root def _connect ( self , current : 'Optional[Node]' , next_node : 'Optional[Node]' ) -> None : if current is None : return else : current . next = next_node # connect self . _connect ( current . left , current . right ) if next_node is not None : self . _connect ( current . right , next_node . left ) else : self . _connect ( current . right , None )
```