Populating Next Right Pointers In Each Node - Leetcode Solution

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:

Input:

 1

/
2 3 / \
4 5 7

Output:

 1 -> NULL

/
2 -> 3 -> NULL / \
4-> 5 -> 7 -> NULL 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.

Note:

You may only use constant extra space. Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Solution:

One of the simplest solutions to this problem can be solving it by using level order traversal approach. We can use a queue to store the nodes at each level and then connect the nodes in a level as they come out of the queue. While using a queue might not satisfy the requirement of using constant extra space, it still provides an understandable and quicker solution to this problem.

Code:

class Solution { public: Node* connect(Node* root) { if (root == nullptr) { return nullptr; }

    queue<Node*> q;
    q.push(root);
    
    while (!q.empty()) {
        int size = q.size();
        
        for (int i = 0; i < size; i++) {
            Node* node = q.front();
            q.pop();
            
            if (i < size - 1) {
                node->next = q.front();
            }
            
            if (node->left) {
                q.push(node->left);
            }
            
            if (node->right) {
                q.push(node->right);
            }
        }
    }
    
    return root;
}

};

The above code implements a BFS approach to the problem. At each level, we add all the nodes of the current level to the queue and then connect them to form the linked list. We return the root after completing the traversal as required.

1