Header Ads Widget

Successor | Solution of cracking the coding interview

Rajnish Tripathi 22:01

 Program:-

     Write an algorithm to find the "next" node (i.e. in-order successor ) of a given node in a binary search tree . You may assume that each node has a link to its parent.

Code:-

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

int a[50],k=0;
struct node
{
int data;
node *left ,* right;
};
struct node * root=NULL;
node * CreateNode()
{
node *temp;
temp=new node;
return temp;
}
void BinarySearchTree(int a)
{
struct node *temp,*t;
temp=CreateNode();
temp->data=a;
temp->left=NULL;
temp->right=NULL;
if(root==NULL)
root=temp;
else
{
t=root;
while(t!=NULL)
{
if(t->data>a)
{
if(t->left==NULL)
{
t->left=temp;
t=t->left;
}
t=t->left;
}
else
{
if(t->right==NULL)
{
t->right=temp;
t=t->right;
}
t=t->right;
}
}
}
}
void InorderTraversal(node *t)
{
if(t)
{
InorderTraversal(t->left);
a[k]=t->data;
k++;
InorderTraversal(t->right);
}
}
int main()
{
int n;
int b;
cout<<"Enter the number of nodes "<<endl;
cin>>n;
cout<<"Enter the values of nodes"<<endl;
for(int i=0;i<n;i++)
{
cin>>b;
BinarySearchTree(b);
}
InorderTraversal(root);
cout<<"Enter the node "<<endl;
cin>>b;
for(int i=0;i<k;i++)
{
if(b==a[i])
{
cout<<"Successor of "<<a[i]<<" is "<<a[i+1];
}
}
return 0;
}


Output:-

Enter the number of nodes
7
Enter the values of nodes
10 8 51 7 9 42 61
Enter the node
51
Successor of 51 is 61



Recommended Post:-

         MCQs:-



Tags:

Post a Comment

0 Comments