Populating Next Right Pointers in Each Node – BFS Solution in C++ 🚀
Intuition
The goal is to connect each node to its next right node in a perfect binary tree. If there’s no next right node, it should remain NULL.
This is a clas
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
1) The goal is to connect each node to its next right node in a perfect binary tree. If there’s no next right node, it should remain NULL.
2) This is a classic level-order traversal problem, where we process each level of the tree and connect adjacent nodes at the same level.
3) We can achieve this by using a queue (BFS) to traverse the tree level by level and updating the next pointers.
# Approach
<!-- Describe your approach to solving the problem. -->
1) Handle Edge Case:
    i) If the tree is empty (i.e., root == nullptr), return nullptr.
2) Use a Queue for Level-Order Traversal (BFS):
    i) Start with the root node and push it to the queue.
    ii) Process nodes level by level:
    -> For each node, check if it’s the last node in the current level. If not, set its next pointer to the node that comes next in the queue.
-> If the node has left and right children, push them into the queue for processing in the next level.
3) Continue Until the Queue is Empty:
    i) The process ensures that all nodes at a level are connected in a chain via their next pointers.
    ii) After the entire tree is processed, return the root, which now has all its next pointers correctly set.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Each node is processed once, and each operation inside the loop (push, pop, and next assignment) takes constant time. Hence, the time complexity is O(n), where n is the number of nodes in the tree.
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
Each node is processed once, and each operation inside the loop (push, pop, and next assignment) takes constant time. Hence, the time complexity is O(n), where n is the number of nodes in the tree.
# Code
```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==nullptr) return {};

        queue<Node*> q;
        q.push(root);
        
        while(!q.empty()){
            int n = q.size();

            for(int i=0;i<n;i++){
                Node* t = q.front();
                q.pop();

                if(i!=n-1){
                    t->next=q.front();
                }

                if(t->left) q.push(t->left);

                if(t->right) q.push(t->right);
            }
        }
        return root;
    }
};
```
```Java []
class Solution {
    public Node connect(Node root) {
        if (root == null) return null;

        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            int n = q.size();

            for (int i = 0; i < n; i++) {
                Node node = q.poll();

                if (i != n - 1) {
                    node.next = q.peek();
                }

                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
        }
        return root;
    }
}
```
['Linked List', 'Tree', 'Breadth-First Search', 'Binary Tree', 'C++', 'Java']