C, Recursive, O(1) space


  • 0
    M

    First solving this problem for an easier use case helps. So the solution posted right below is for a balanced binary tree.

    void connect(struct TreeLinkNode *root)
    {
        /* Validate node */
        if (!root) return;
    
        /* Point left child to right : Best case */
        if (root->left)
            root->left->next = root->right;
                
        /* If right child is valid, then traverse parent's siblings to 
        find the next pointer */
        if (root->right && root->next)
            root->right->next = root->next->left;
        
        /* First going right will populate "next" pointers, then left */
        connect(root->right);
        connect(root->left);
    }
    

    The problem is essentially about locating the next sibling. To find that sibling of a node we need the next sibling of its parent. So the idea is to do a DFS while furnishing the root->next pointers and then we can use those links to locate the siblings for its children.

    As you can see above, we do a DFS traversal from right to the left. Why right to left? Simply because the pointers are from left to right, the idea is to have these next pointers ready and then use them during subsequent traversals.

    Below we have the full solution:

    struct TreeLinkNode *GetNext(struct TreeLinkNode *root)
    {
        if (!root) return NULL; // validate
        
        /* Find the next parent with a child */
        while (root && !root->left && !root->right) root = root->next;
        return root ? (root->left ? root->left : root->right) : NULL;
    }
    void connect(struct TreeLinkNode *root)
    {
        /* Validate node */
        if (!root) return;
    
        /* Point left child to right : Best case */
        if (root->left && root->right)
            root->left->next = root->right;
    
        /* If find the next node by traversing the siblings of the parent. */
        else if (root->left)
            root->left->next = GetNext(root->next);
                
        /* If right child is valid, then traverse parent's siblings to 
        find the next pointer */
        if (root->right)
            root->right->next = GetNext(root->next);
        
        /* First going right will populate "next" pointers */
        connect(root->right);
        connect(root->left);
    }
    

    Now if the tree is not balanced, then we cannot rely on root->next->left pointer to be valid. So we generalize this indirection by using a helper function GetNext. The basic DFS approach remains the same, but now we handle additional cases where siblings might be missing.

    If visualization helps, then imagine this algorithm as working up a swarm -- top to bottom and in right to left direction.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.