**Inorder successor of node in binary search tree **

Inorder traversal of tree visits left subtree first, then root node and then right subtree. Given a binary search tree, **find inorder successor of a node. **

Inorder successor of a node is visited after the node in inorder traversal of binary search tree. In other words, it would be the next larger node in binary search tree.

For example. if we take below tree as an example and do inorder traversal of it, traversal will be: 4,6,8,10,12,14,15.

If inorder successor of a node is asked, return next element in traversal. What is inorder successor if node 20? It’s 22. What about 30? It’s 37.

From description, algorithm is almost clear. Traverse entire tree in inorder and store it in an array. Whenever successor of a node is asked. search that in array and return its next element. Also, keep in mind that inorder traversal of a binary search tree is in sorted order, so binary search algorithm can be used to search a node. Overall complexity of this algorithm is dominated by traversal itself which is O(n) and with extra space requirement of O(n).

What if we don’t want to pre-scan tree and store it? This is a valid scenario when tree is modified frequently in between queries for inorder successor. In that case, previously stored traversal will be waste and we need to do another one. That is hell lot of computing wastage, not to mentioned extra space being used. Can we do better? Let’s take a tree and see if we can figure out some pattern? Candidates for inorder successor of a node are as follows:

*If there is right subtree of node, output is left most child in the right subtree.**If there is no right subtree, output is the node where last left turn was taken to reach given node.*

First and second conditions are mutually exclusive that means, if first is true then second does not hold and vice-a-versa.

What if node given is right most node in tree? In that case both conditions will return NULL as there is no right subtree and there was no left turn taken to reach the node.

To summarize algorithm: Traverse to the node and keep track of node last left turn. Once at node, check if there is right subtree, if yes, find minimum in right subtree and return. If not, then return node last left turn was taken.

Let’s see some examples, inorder successor of 8 is 10, because last left was taken at 10 and there is no right sub tree.

Here, inorder successor of 12 is 14, because last left was taken at 14 and there is no right subtree

Here inorder successor of 4 is 6, last left was taken at node 6.

What is inorder successor of 10. Since 10 has right subtree, find minimum element in right subtree. So inorder successor of 10 will be 12, of 14 is 15 and of 6 would be 8.

**Algorithm to find inorder successor**

1. Start with root. Initialize successor as NULL. 2. If given node less than root, then search on left side and update successor. 3. If node is greater than root, then search in right part, don't update successor. 4. When reached at node : 4.1 If node has right subtree, return minimum node on right subtree. 4.2 Else return successor.

#include<stdio.h> #include<stdlib.h> struct node{ int value; struct node *left; struct node *right; }; typedef struct node Node; //this function finds the minimum node in given tree rooted at node root Node * findMinimum(Node *root){ if(!root) return NULL; /* Minimum node is left most child. hence traverse down till left most node of tree. */ while(root->left) root = root->left; // return the left most node return root; } /* This function implements the logic described in algorithm to find inorder successor of a given node */ Node *inorderSuccessor(Node *root, int K){ Node *successor = NULL; Node *current = root; if(!root) return NULL; while(current->value != K){ /* If node value is greater than the node which are looking for, then go to left sub tree Also when we move left, update the successor pointer to keep track of 1st left turn */ if(current->value >K){ successor = current; current= current->left; } /* Else take right turn and no need to update successor pointer */ else current = current->right; } /*Once we reached at the node for which inorder successor is to be found, check if it has right sub tree, if yes then find the minimum in that right sub tree and return right node Else last left turn taken node is already stored in successor pointer and will be returned*/ if(current && current->right){ successor = findMinimum(current->right); } return successor; } Node * createNode(int value){ Node *newNode = (Node *)malloc(sizeof(Node)); newNode->value = value; newNode->right= NULL; newNode->left = NULL; return newNode; } Node * addNode(Node *node, int value){ if(node == NULL){ return createNode(value); } else{ if (node->value > value){ node->left = addNode(node->left, value); } else{ node->right = addNode(node->right, value); } } return node; } /* Driver program for the function written above */ int main(){ Node *root = NULL; int n = 0; //Creating a binary tree root = addNode(root,30); root = addNode(root,20); root = addNode(root,15); root = addNode(root,25); root = addNode(root,40); root = addNode(root,37); root = addNode(root,45); Node *successor = inorderSuccessor(root, 40); printf("\n Inorder successor node is : %d ", successor ? successor->value: 0); return 0; }

Complexity of algorithm to find *inorder successor* will be ** O(logN)** in almost balanced binary tree. If tree is skewed, then we have worst case complexity of O(N). However, there is no extra space required.

Please share if there is something wrong or missing. If you are interested in contributing to website or have an interview to share, please contact us.

Pingback: Find two nodes with given sum in binary search tree (2Sum problem) – Algorithms and Me()

Pingback: Threaded binary search tree – Algorithms and Me()

Pingback: Inorder predecessor in binary search tree - Algorithms and Me()

Pingback: Delete node from binary search tree - Algorithms and Me()