# Populating Next Right Pointers in Each Node II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii)
Canonical: https://scaleengineer.com/dsa/problems/populating-next-right-pointers-in-each-node-ii
**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:** [Snowflake](https://scaleengineer.com/companies/snowflake), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Citadel](https://scaleengineer.com/companies/citadel)
---
## 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`.

**Example 1:**

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

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

**Example 2:**

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

**Constraints:**

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

**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)
This approach uses a standard Breadth-First Search (BFS) to traverse the tree level by level. A queue is used to store the nodes of the current level. As we process each node, we connect it to the previously processed node on the same level.
**Time:** O(N) · **Space:** O(W)
**Pros:** The logic is straightforward and follows the standard BFS pattern, making it easy to understand and implement.; It correctly handles any type of binary tree, not just perfect ones.
**Cons:** Violates the follow-up constraint of using only constant extra space.; The space usage can be substantial for very wide trees, potentially leading to memory issues.
### Explanation
We can solve this problem by performing a level order traversal of the tree, which is naturally implemented using a queue. The core idea is to process nodes one level at a time. For each level, we iterate through all its nodes from left to right, keeping track of the previously visited node to establish the `next` connection.

By getting the size of the queue before processing a level, we know exactly how many nodes belong to that level. This allows us to correctly connect nodes within the same level and ensures the `next` pointer of the rightmost node of a level remains `null`.

```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.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            Node prev = null;
            for (int i = 0; i < levelSize; i++) {
                Node current = queue.poll();

                if (prev != null) {
                    prev.next = current;
                }
                prev = current;

                if (current.left != null) {
                    queue.offer(current.left);
                }
                if (current.right != null) {
                    queue.offer(current.right);
                }
            }
        }
        return root;
    }
}
```
### Algorithm
1. If the `root` is `null`, there is nothing to connect, so return `null`.
2. Initialize a queue (e.g., `LinkedList`) and add the `root` node to it.
3. Begin a loop that continues as long as the queue is not empty.
4. At the start of each level, determine the number of nodes on that level by checking the current `queue.size()`. Let's call this `levelSize`.
5. Initialize a `prev` node pointer to `null`. This pointer will keep track of the previous node processed on the current level.
6. Start an inner loop that runs `levelSize` times to process each node of the current level.
7. Inside the inner loop, dequeue a node and call it `current`.
8. If `prev` is not `null`, it means `current` is not the first node on this level. Set `prev.next = current` to link the previous node to the current one.
9. Update `prev` to point to `current`.
10. If `current.left` is not `null`, enqueue it to be processed in the next level.
11. If `current.right` is not `null`, enqueue it as well.
12. Once the inner loop completes, all nodes for the current level are connected. The outer loop then continues to the next level.
13. After the outer loop finishes, return the `root`.

## Constant Space Level by Level Iteration
This optimized approach avoids using a queue and instead utilizes the `next` pointers established in the previous level to traverse the current level. It iterates through the tree level by level, using pointers to keep track of the head of the current level and to build the connections for the next level.
**Time:** O(N) · **Space:** O(1)
**Pros:** Achieves optimal O(1) extra space complexity, satisfying the follow-up constraint.; Maintains an efficient O(N) time complexity.
**Cons:** The logic is more complex than the BFS approach, involving multiple pointers and a dummy node, which can be harder to reason about initially.
### Explanation
This approach achieves the O(1) space complexity requirement by cleverly using the `next` pointers that are already established. We can think of the process as having a pointer, `levelHead`, that always points to the start of the current level. We then use another pointer, `curr`, to traverse this level from left to right using the `next` links.

As we traverse the current level, we establish the `next` connections for the level below it. To simplify linking the children, we use a `dummy` node. This `dummy` node acts as a sentinel, providing a fixed starting point for the linked list of the next level. A `nextLevelCurr` pointer starts at the `dummy` node and is used to append the children of the nodes from the current level.

After iterating through the entire current level, `dummy.next` will point to the first node of the next level. We then update `levelHead` to `dummy.next` and repeat the process for the subsequent 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) {
        Node levelHead = root;
        while (levelHead != null) {
            // Dummy node to anchor the start of the next level
            Node dummy = new Node(0);
            Node nextLevelCurr = dummy;
            Node curr = levelHead;

            // Iterate through the current level
            while (curr != null) {
                if (curr.left != null) {
                    nextLevelCurr.next = curr.left;
                    nextLevelCurr = nextLevelCurr.next;
                }
                if (curr.right != null) {
                    nextLevelCurr.next = curr.right;
                    nextLevelCurr = nextLevelCurr.next;
                }
                curr = curr.next;
            }
            // Move to the start of the next level
            levelHead = dummy.next;
        }
        return root;
    }
}
```
### Algorithm
1. Initialize `levelHead = root`. This pointer marks the start of the current level being processed.
2. Start an outer loop that continues as long as `levelHead` is not `null`.
3. Inside the loop, create a `dummy` node. This node's `next` pointer will be used to build the linked list for the next level. Initialize a `nextLevelCurr` pointer to this `dummy` node.
4. Initialize a `curr` pointer to `levelHead` to iterate through the nodes of the current level using their `next` pointers.
5. Start an inner loop that continues as long as `curr` is not `null`.
6. Inside the inner loop, check for children of the `curr` node:
   a. If `curr.left` is not `null`, append it to the next level's list: `nextLevelCurr.next = curr.left`, and then advance the pointer: `nextLevelCurr = nextLevelCurr.next`.
   b. If `curr.right` is not `null`, do the same: `nextLevelCurr.next = curr.right`, and `nextLevelCurr = nextLevelCurr.next`.
7. Move to the next node on the current level: `curr = curr.next`.
8. After the inner loop finishes, the `next` pointer of the `dummy` node (`dummy.next`) will point to the head of the now-connected next level.
9. Update `levelHead` to `dummy.next` to move the processing to the next level.
10. Once the outer loop finishes, all levels have been processed. Return the original `root`.

# Solutions
### CSharp

```csharp
/* // Definition for a Node. public 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; } } */ public class Solution { private Node prev , next ; public Node Connect ( Node root ) { Node node = root ; while ( node != null ) { prev = null ; next = null ; while ( node != null ) { modify ( node . left ); modify ( node . right ); node = node . next ; } node = next ; } return root ; } private void modify ( Node curr ) { if ( curr == null ) { return ; } if ( next == null ) { next = curr ; } if ( prev != null ) { prev . next = curr ; } prev = curr ; } }
```

### 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 { private Node prev , next ; public Node connect ( Node root ) { Node node = root ; while ( node != null ) { prev = null ; next = null ; while ( node != null ) { modify ( node . left ); modify ( node . right ); node = node . next ; } node = next ; } return root ; } private void modify ( Node curr ) { if ( curr == null ) { return ; } if ( next == null ) { next = curr ; } if ( prev != null ) { prev . next = curr ; } prev = curr ; } }
```

### 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 ) { Node * node = root ; Node * prev = nullptr ; Node * next = nullptr ; auto modify = [ & ]( Node * curr ) { if ( ! curr ) { return ; } if ( ! next ) { next = curr ; } if ( prev ) { prev -> next = curr ; } prev = curr ; }; while ( node ) { prev = next = nullptr ; while ( node ) { modify ( node -> left ); modify ( node -> right ); node = node -> next ; } node = next ; } 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 """ class Solution : def connect ( self , root : "Node" ) -> "Node" : def modify ( curr ): nonlocal prev_node , next_node if curr is None : return if next_node is None : # next level's first node next_node = curr # "if next_node is None" logic can be replaced by: # next_node = next_node or curr if prev_node : prev_node . next = curr prev_node = curr node = root while node : prev_node = next_node = None while node : # process for every level modify ( node . left ) modify ( node . right ) node = node . next node = next_node return root # use dummyHead.next to find each level's first node class Solution : def connect ( self , root : 'Node' ) -> 'Node' : dummyHead = Node ( 0 ) pre = dummyHead real_root = root while root : if root . left : # @note: here pre is same as dummyHead, pointing to 1st node of this level. this is before pre is updated to be other nodes pre . next = root . left pre = pre . next if root . right : pre . next = root . right pre = pre . next root = root . next if not root : # reach the end of current layer # shift pre back to the beginning, # get ready to point to the first element in next layer, # just like the same code before while loop pre = dummyHead # root comes down one level below to the first available non null node root = dummyHead . next # reset dummyhead back to default null, so that later it will point to next level's first node dummyHead . next = None return real_root ############### """ # Definition for a Node. 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 """ from collections import deque class Solution : # recursion, dfs def connect ( self , root : 'Node' ) -> 'Node' : if not root : return None # Initialize a queue with the root node and its level (0). queue = deque ([( root , 0 )]) # Process nodes level by level. while queue : current_node , level = queue . popleft () # If there's another node in the queue with the same level, # connect the current node's next pointer to the next node in the queue. if queue and queue [ 0 ][ 1 ] == level : current_node . next = queue [ 0 ][ 0 ] # Enqueue left and right children if they exist, along with their level. if current_node . left : queue . append (( current_node . left , level + 1 )) if current_node . right : queue . append (( current_node . right , level + 1 )) return root ############### # Definition for binary tree with next pointer. # class TreeLinkNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # self.next = None class Solution : # @param root, a tree link node # @return nothing def connect ( self , root ): p = root pre = None head = None while p : if p . left : if pre : pre . next = p . left pre = p . left if p . right : if pre : pre . next = p . right pre = p . right if not head : head = p . left or p . right if p . next : p = p . next else : p = head head = None pre = None
```