Successor/Predecessor Rules in BST/BT

Write programs to find inorder successor and inorder predecessor of a binary search tree

Also find

i)preorder sucessor and  preorder predecessor

ii)postorder successor and postorder predecessor

Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree. 

For example, if the given tree is following Binary Tree and key is 7, then your function should print 4, 2 and 1.

              1
            /   \
          2      3
        /  \
      4     5
     /
    7

Inorder successor of BST:

Method 1:Without Parent Pointer-Search from Root

1) If right subtree of node is not NULL, then succ lies in right subtree. Do following.

Go to right subtree and return the node with minimum key value in right subtree.

2) If right sbtree of node is NULL, then start from root and us search like technique. Do following.

Travel down the tree, if a node’s data is greater than root’s data then go right side, otherwise go to left side

Code:

.

struct node * inOrderSuccessor(struct node *root, struct node *n)

{

    if( n->right != NULL )

        return minValue(n->right);

    struct node *succ = NULL;

    while (root != NULL)    //Start from the root

    {

        if (n->data < root->data)

        {

            succ = root;

            root = root->left;

        }

        else if (n->data > root->data)

            root = root->right;

        else

           break;

    }

    return succ;

}

Time Complexity:O(h)-h is height of tree

References:http://net.pku.edu.cn/~course/cs101/2007/resource/Intro2Algorithm/book6/chap13.htm

Method 2:With Parent Pointer 

1) If right subtree of node is not NULL, then succ lies in right subtree. Do following.
Go to right subtree and return the node with minimum key value in right subtree.
2) If right sbtree of node is NULL, then succ is one of the ancestors. Do following.
Travel up using the parent pointer until you see a node which is left child of it’s parent. The parent of such a node is the succ.

Code:

struct node

{

    int data;

    struct node* left;

    struct node* right;

    struct node* parent;

};

struct node * inOrderSuccessor(struct node *root, struct node *n)

{

  if( n->right != NULL )

    return minValue(n->right);

  struct node *p = n->parent;

  while(p != NULL && n == p->right)

  {

     n = p;

     p = p->parent;

  }

  return p;

}

struct node * minValue(struct node* node) {

  struct node* current = node;

  while (current->left != NULL)   //Leftmost node

{  

    current = current->left;

  }

  return current;

}

Time Complexity:O(h) 

Inorder Predecessor of BST:

Method 1:Start from Root
struct node * inOrderPredecessor(struct node *root, struct node *n)
{
if( n->left != NULL )
return maxValue(n->left);
struct node *pred=NULL;
while(root)
{
if(n->data < root->data)
root=root->left;
else if(n->data > root->data)
{
pred=root;
root=root->right;
}
else
break;
}
return pred;
}
Time:O(logn) in Avg. & O(N) in worst

Method 2:Using Parent

1.Find The Minimum value in BSt if given Node has the same value we are done as
the minimum value in BST is left most leaf & can't have any predecessor :)
2.Check if node->Left is leaf or not if yes then node->left is our answer
3.if n is right child then its parent will be inorder predecessor
4.else if all above case fail then inorder predecessor be maximum value in left
subtree of given node N.

Code:
struct node
{
int data;
struct node* left;
struct node* right;
struct node* parent;
};

struct node* minValue(struct node* node);

int isLeaf(struct node* root)
{
if(root->left==NULL && root->right==NULL)
return 1;
return 0;
}

struct node* maxValue(struct node* node)
{
struct node* current = node;

 while (current->right!= NULL)  //loop down to find the leftmost leaf
{
current = current->right;
}
return current;
}

struct node* inOrderPredecessor(struct node *root, struct node *n)
{
// step 1 of the above algorithm

if(n==minValue(root))
{
printf("No Inorder Predecessor Possible");
return NULL;
}

//2nd step of above algo

if(isLeaf(n->left))
return n->left;

//3rd step if n is right children of parent

struct node *p =n->parent;
if(n == p->right)
return p;

// step 4 of the above algorithm if all above not satisfied then predecessor exist in right
return maxValue(n->left);
}
Time Complexity:O(logn) Time in Avg.Case & O(N) time in Worst Case Skew Tree