{"id":27309,"date":"2018-01-20T21:23:33","date_gmt":"2018-01-20T15:53:33","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27309"},"modified":"2018-01-20T21:23:33","modified_gmt":"2018-01-20T15:53:33","slug":"c-program-inorder-successor-binary-search-tree","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-program-inorder-successor-binary-search-tree\/","title":{"rendered":"C Program-Inorder Successor in Binary Search Tree"},"content":{"rendered":"

In Binary Tree, Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inoorder traversal.<\/span>
\nIn Binary Search Tree, Inorder Successor of an input node can also be defined as the node with the smallest key greater than the key of input node. So, it is sometimes important to find next node in sorted order.<\/p>\n

In the above diagram, inorder successor of 8 is 10, inorder successor of 10 is 12 and inorder successor of 14 is 20.<\/p>\n

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.<\/strong><\/p>\n

Method 1 (Uses Parent Pointer)<\/strong>
\nIn this method, we assume that every node has parent pointer.<\/p>\n

The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.<\/p>\n

Input: node, root \/\/ node is the node whose Inorder successor is needed.
\noutput: succ \/\/ succ is Inorder successor of node.<\/p>\n

1)<\/strong> If right subtree of node is not NULL, then succ lies in right subtree. Do following.
\nGo to right subtree and return the node with minimum key value in right subtree.
\n2)<\/strong> If right sbtree of node is NULL, then succ is one of the ancestors. Do following.
\nTravel up using the parent pointer until you see a node which is left child of it\u2019s parent. The parent of such a node is the succ.<\/p>\n[ad type=”banner”]\n

Implementation<\/strong>
\nNote that the function to find InOrder Successor is highlighted (with gray background) in below code.<\/p>\n

C Programming<\/span> <\/div> 
#include <stdio.h>#include <stdlib.h>  \/* A binary tree node has data, pointer to left child   and a pointer to right child *\/struct node{    int data;    struct node* left;    struct node* right;    struct node* parent;}; struct node * minValue(struct node* node);  struct node * inOrderSuccessor(struct node *root, struct node *n){  \/\/ step 1 of the above algorithm   if( n->right != NULL )    return minValue(n->right);   \/\/ step 2 of the above algorithm  struct node *p = n->parent;  while(p != NULL && n == p->right)  {     n = p;     p = p->parent;  }  return p;} \/* Given a non-empty binary search tree, return the minimum data      value found in that tree. Note that the entire tree does not need    to be searched. *\/struct node * minValue(struct node* node) {  struct node* current = node;    \/* loop down to find the leftmost leaf *\/  while (current->left != NULL) {    current = current->left;  }  return current;} \/* Helper function that allocates a new node with the given data and     NULL left and right pointers. *\/struct node* newNode(int data){  struct node* node = (struct node*)                       malloc(sizeof(struct node));  node->data   = data;  node->left   = NULL;  node->right  = NULL;  node->parent = NULL;     return(node);} \/* Give a binary search tree and a number, inserts a new node with        the given number in the correct place in the tree. Returns the new    root pointer which the caller should then use (the standard trick to     avoid using reference parameters). *\/struct node* insert(struct node* node, int data){  \/* 1. If the tree is empty, return a new,      single node *\/  if (node == NULL)    return(newNode(data));  else  {    struct node *temp;       \/* 2. Otherwise, recur down the tree *\/    if (data <= node->data)    {             temp = insert(node->left, data);         node->left  = temp;         temp->parent= node;    }    else    {        temp = insert(node->right, data);        node->right = temp;        temp->parent = node;    }          \/* return the (unchanged) node pointer *\/    return node;  }}   \/* Driver program to test above functions*\/int main(){  struct node* root = NULL, *temp, *succ, *min;   \/\/creating the tree given in the above diagram  root = insert(root, 20);  root = insert(root, 8);  root = insert(root, 22);  root = insert(root, 4);  root = insert(root, 12);  root = insert(root, 10);    root = insert(root, 14);      temp = root->left->right->right;   succ =  inOrderSuccessor(root, temp);  if(succ !=  NULL)    printf("\\n Inorder Successor of %d is %d ", temp->data, succ->data);      else    printf("\\n Inorder Successor doesn't exit");   getchar();  return 0;}<\/code><\/pre> <\/div>\n
Output of the above program:<\/strong>
\nInorder Successor of 14 is 20<\/em><\/p>\n
Time Complexity:<\/strong> O(h) where h is height of tree.<\/p>\n[ad type=”banner”]\n
Method 2 (Search from root) <\/strong>
\nParent pointer is NOT needed in this algorithm. The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.<\/p>\n
Input: node, root<\/em> \/\/ node <\/em>is the node whose Inorder successor is needed.
\noutput: succ <\/em>\/\/ succ <\/em>is Inorder successor of node<\/em>.<\/p>\n
1)<\/strong> If right subtree of node <\/em>is not NULL<\/em>, then succ <\/em>lies in right subtree. Do following.
\nGo to right subtree and return the node with minimum key value in right subtree.
\n2) <\/strong>If right sbtree of node <\/em>is NULL, then start from root and us search like technique. Do following.
\nTravel down the tree, if a node\u2019s data is greater than root\u2019s data then go right side, otherwise go to left side.<\/p>\n
 
 C Programming<\/span> <\/div> 
struct node * inOrderSuccessor(struct node *root, struct node *n){    \/\/ step 1 of the above algorithm    if( n->right != NULL )        return minValue(n->right);     struct node *succ = NULL;     \/\/ Start from root and search for successor down the tree    while (root != NULL)    {        if (n->data < root->data)        {            succ = root;            root = root->left;        }        else if (n->data > root->data)            root = root->right;        else           break;    }     return succ;}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
C Program – In order Successor in Binary Search Tree – Binary Search Tree – In order Successor is NULL for the last node in In order traversal.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,80126,69866,1],"tags":[81419,81420,81412,81414,81413,81418,81415,80862,81417,81416],"class_list":["post-27309","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-binary-search-tree","category-c-programming","category-coding","tag-inorder-successor-in-bst","tag-inorder-successor-in-bst-java","tag-inorder-successor-in-bst-leetcode","tag-inorder-successor-without-parent-pointer","tag-inorder-traversal-in-bst","tag-postorder-successor","tag-preorder-successor","tag-successor-and-predecessor-in-binary-search-tree","tag-tree-predecessor-pseudocode","tag-what-is-successor-and-predecessor"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27309","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27309"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27309\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27309"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27309"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27309"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}