Populating Next Right Pointersin Each Node I I Algorithm

The Populating Next Right Pointers in Each Node II Algorithm is an extension of the first version, where the given binary tree can be a general one, not necessarily a perfect binary tree. This algorithm aims to populate each next pointer in every node, connecting the nodes at the same level, from left to right. The primary objective of this algorithm is to enhance the traversal of a binary tree, enabling a more efficient and convenient access to sibling nodes at each level. The implementation of this algorithm can be done using a level order traversal, which is usually achieved through a queue or a BFS (Breadth-First Search) approach. In this case, we create an auxiliary node called 'dummy' which initially points to the first node at each level, and a variable 'current' that iterates through the nodes at the current level. As we traverse each level, we connect the next pointers of the nodes, and when we reach the end of a level, we update the 'dummy' node to point to the first node of the next level, and reset the 'current' node to the 'dummy' node. This process is repeated until all the nodes have their next pointers populated, thus connecting all the nodes at the same level from left to right.
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root == NULL) {
            return;
        }
        TreeLinkNode* leftmost = root;
        while (leftmost) {
            TreeLinkNode* node = leftmost;
            TreeLinkNode* prev = NULL;
            leftmost = NULL;
            while (node) {
                if (node->left) {
                    if (leftmost == NULL) {
                        leftmost = node->left;
                    }
                    if (prev == NULL) {
                        prev = node->left;
                    } else {
                        prev->next = node->left;
                        prev = node->left;
                    }
                }
                if (node->right) {
                    if (leftmost == NULL) {
                        leftmost = node->right;
                    }
                    if (prev == NULL) {
                        prev = node->right;
                    } else {
                        prev->next = node->right;
                        prev = node->right;
                    }
                }
                node = node->next;
            }
        }
    }
};

LANGUAGE:

DARK MODE: