C++ program to find inorder successor in binary search tree with recursion














































C++ program to find inorder successor in binary search tree with recursion



#include <bits/stdc++.h> 
using namespace std;

struct node 
int data; 
struct node* left; 
struct node* right; 
struct node* parent; 
}; 

struct node * minValue(struct node* node) 
struct node* current = node; 

while (current->left != NULL) 
current = current->left; 
return current; 
}

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* getNode(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); 

struct node* insert(struct node* node, int data) 

if (node == NULL) 
return(getNode(data)); 
else
struct node *temp; 

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 node; 
int main() 
struct node* root = NULL, *temp, *Successor, *min; 

root = insert(root, 30); 
root = insert(root, 18); 
root = insert(root, 32); 
root = insert(root, 14); 
root = insert(root, 22); 
root = insert(root, 20); 
root = insert(root, 24);  
temp = root->left; 

Successor = inOrderSuccessor(root, temp); 
if(Successor != NULL) 
cout<<"Inorder Successor of "<<temp->data<<" is "<<Successor->data;  
else
cout<<"Inorder Successor doesn't exit"; 

return 0; 
/*           30
              /   \
             18    32
            /  \  
           14  22
                  / \
              20  24
                        */
// OUTPUT ::
// Inorder Successor of 18 is 20


Comments