Algo#4: Postorder Successor in Binary Tree

Postorder Successor value for any node X means value of node Y that comes just after node X while doing Postorder traversal. For given tree in figure, postorder traversal (Left Right Root) would be : 4 5 2 6 3 1. We can search postorder successor for any node by just looking at this traversal output. E.G. postorder successor of node '4' is node '5' because '5' appears after '4' in given traversal.

But in real life we encounter Postorder Successor to be search for randomly any node, and if we go by this method of doing postorder traversal first then giving successor  it would be inefficient because of its time complexity of O(n) in large trees. So we need some method which can return Postorder successor randomly for any node without doing traversal explicitly in less time complexity.

Luckily postorder traversal follows some pattern which can help us in giving Postorder Successor for any node without doing traversal at all.

Following is simple algorithm for finding Postorder Successor of binary tree.

Step 1: If current root is NULL, then succ(current root) is NULL.

Step 2: If current root is target node for which we are looking for successor.

        2.1: If current root is the root of the tree, succ(current root) is undefined.

        2.2: Otherwise, if current root is a right child, succ(current root) is parent(current root).

        2.3: Otherwise current root is a left child and the following applies:

           2.3.1: If u has a right sibling, r, succ(current root) is the leftmost leaf in r's sub-tree

           2.3.2: Otherwise succ(current root) is parent(current root).
           2.3.3: If none of above applies, then succ(current root) doesn't exist.

Step 3: Current root is not the target node for which we are looking predecessor.

        3.1: Search target node and its predecessor in left side of tree recursively, and return if found.

        3.2: Search target node and its predecessor in right side of tree recursively, and return.

Following is implementation of above algorithm in c language.

/*
Algo#4: Postorder Successor in Binary Tree

Description: Find Postorder Successor value in given Biinary Tree.
*/
#include 
#include 

typedef struct node
{
    int data;
    struct node *left,*right;
} Node;

Node *leftmostLEAFnotNODE(Node *root)
{
    while (root->left || root->right)
    {
        if(root->left) root=root->left;
        else root=root->right;
    }

    return root;
}

Node *postorderSuccessorRec(Node *root, int key,Node *direct_parent, Node *parent,Node * treeroot)
{
    //Case 1: If current root is NULL, then succ(current root) is NULL.
    if (root==NULL)
        return 0;
    //Case 2: If current root is target node for which we are looking for successor.
    if (root->data == key)
    {
        //Case 2.1: If current root is the root of the tree, succ(current root) is undefined.
        if(root == treeroot)
            return NULL;
        //Case 2.2: Otherwise, if current root is a right child, succ(current root) is parent(current root).
        else if(direct_parent != NULL && direct_parent->right==root)
            return direct_parent;
        //Case 2.3: Otherwise current root is a left child and the following applies:

        //Case 2.3.1: If u has a right sibling, r, succ(current root) is the leftmost leaf in r's sub-tree
        else if(direct_parent != NULL && direct_parent->left==root && direct_parent->right!=NULL)
            return leftmostLEAFnotNODE(direct_parent->right);
        //Case 2.3.2: Otherwise succ(current root) is parent(current root).
        else if(direct_parent != NULL && direct_parent->left==root && direct_parent->right==NULL)
            return direct_parent;
        //Case 2.3.3: If none of above applies, then succ(current root) doesn't exist.
        else
            return NULL;
    }
    //Case 3: Current root is not the target node for which we are looking successor.
    else
    {
        //Case 3.1: Search target node and its successor in left side of tree recursively, and return if found.
        Node *left=postorderSuccessorRec(root->left,key,root,root,treeroot);
        if (left)
            return left;
        //Case 3.2: Search target node and its successor in right side of tree recursively, and return.
        return postorderSuccessorRec(root->right,key,root,parent,treeroot);
    }
}

Node *postorderSuccessor(Node *root, int key)
{
    return postorderSuccessorRec(root,key,NULL,NULL,root);
}

struct node* newNode(int data)
{
  struct node* node = (struct node*)  malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}


int main()
{

  /*
            1
          /   \
        2      3
      /  \    /
    4     5  6
  */
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);

  struct node * succ;
  succ = postorderSuccessor(root, 3);
  printf("Postorder Successor of %d is : %d\n",3,succ?succ->data:0);

  succ = postorderSuccessor(root, 4);
  printf("Postorder Successor of %d is : %d\n",4,succ?succ->data:0);

  getchar();
  return 0;
}

Please write comments if you find anything wrong or you want to add something more related to this topic.