Connecting Nodes at the Same Level

The problem asks us to use next pointers to connect nodes at the same level in a tree. The main challenge is that space complexity must stay constant.

Type 1: Perfect Binary Tree

This works for a complete binary tree where every node has an adjacent node. If a node has a left child, its next pointer goes to the right child. If it has a right child, the next pointer can be null or point to the left child of the parent’s next node.

Node* connect(Node* root) {
    if (root == NULL) return root;
    Node *pre=root;
    Node *cur=NULL;

    while(pre->left) {
        cur = pre;
        while(cur) {
            cur->left->next = cur->right;
            if (cur->next) cur->right->next = cur->next->left;
            cur=cur->next;
        }
        pre = pre->left;
    }
    return root;
}

Type 2: Arbitrary Binary Tree

This handles any binary tree shape where heights can vary. We just need extra boundary checks.

Node* connect(Node* root) {
    if (root == NULL) return root;
    Node* pre = root;
    Node* cur;
    pre->next = NULL;
    while(pre!=NULL) {
        cur = pre;
        while(cur != NULL) {
            if (cur->left) {
                if (cur->right)
                    cur->left->next = cur->right;
                else
                    cur->left->next = getNext(cur);
            }

            if (cur->right) {
                cur->right->next = getNext(cur);
            }
            cur = cur->next;        
        }
        if (pre->left)
            pre = pre->left;
        else if (pre->right)
            pre = pre->right;
        else
            pre = getNext(pre);
    }
    return root;
}

// Keep looking through sibling nodes at higher levels
// Return left child first, then right child
// Return null if nothing found
Node* getNext(Node* node) {
    node = node->next;

    while(node!=NULL) {
        if (node->left)
            return node->left;
        else if (node->right)
            return node->right;
        node = node->next;
    }
    return NULL;
}

#tree

Compare Version Numbers with StringStream Convert Sorted List to Balanced Binary Search Tree