Given a binary tree with extra field "next pointer" in node, populate the next pointer to the nodes inorder successor

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/populate-next-pointer-to-inorder-successor-in-binary-tree/.

Problem : Given a Binary tree where each node has an extra field (node * next), write a function that puts the inorder successor of that node in the next pointer.
This is how our binary tree node looks like :

struct node
{
  int data;
  struct node* left;
  struct node* right;
  struct node* next;
}

Initially, all next pointers have NULL values. Your function should fill these next pointers so that they point to inorder successor.

Solution
This can be petty easily done using the general Inorder traversal algorithm of binary trees. Please refer what is inorder successor or the node here.



Solution (Use Reverse Inorder Traversal)
Traverse the given tree in reverse inorder traversal and keep track of previously visited node. When a node is being visited, assign previously visited node as next.

/* Set next of p and all descendents of p by traversing them in reverse Inorder */
void populateNext(struct node* p)
{
    // The first visited node will be the rightmost node
    // next of the rightmost node will be NULL
    static struct node *next = NULL;
 
    if (p)
    {
        // First set the next pointer in right subtree
        populateNext(p->right);
 
        // Set the next as previously visited node in reverse Inorder
        p->next = next;
 
        // Change the prev for subsequent node
        next = p;
 
        // Finally, set the next pointer in left subtree
        populateNext(p->left);
    }
}

We can avoid the use of static variable by passing reference to next as paramater.

// An implementation that doesn't use static variable
 
// A wrapper over populateNextRecur
void populateNext(struct node *root)
{
    // The first visited node will be the rightmost node
    // next of the rightmost node will be NULL
    struct node *next = NULL;
 
    populateNextRecur(root, &next);
}
 
/* Set next of all descendents of p by traversing them in reverse Inorder */
void populateNextRecur(struct node* p, struct node **next_ref)
{
    if (p)
    {
        // First set the next pointer in right subtree
        populateNextRecur(p->right, next_ref);
 
        // Set the next as previously visited node in reverse Inorder
        p->next = *next_ref;
 
        // Change the prev for subsequent node
        *next_ref = p;
 
        // Finally, set the next pointer in right subtree
        populateNextRecur(p->left, next_ref);
    }
}

Time Complexity: O(n)