-
Notifications
You must be signed in to change notification settings - Fork 0
/
InorderTraversal.cpp
114 lines (114 loc) · 1.74 KB
/
InorderTraversal.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<iostream>
using namespace std;
struct Node{
int data;
Node *left;
Node *right;
};
Node* Search(Node *root,int data)
{
if(root==NULL)
{
return NULL;
}
else
if(root->data==data)
{
return root;
}
else
if(root->data<data)
{
return Search(root->right,data);
}
else
return Search(root->left,data);
}
Node *SearchMin(Node *root)
{
if(root==NULL)
{
return NULL;
}
while(root->left!=NULL)
{
root=root->left;
}
return root;
}
Node *Successor(Node *root,int data)
{
Node *Current=Search(root,data);
if(Current==NULL)
{
return NULL;
}
if(Current->right!=NULL)
{
return SearchMin(Current->right);
}
else
{
Node *successor=NULL;
Node* ancestor=root;
while(ancestor!=Current)
{
if(Current->data<ancestor->data){
successor=ancestor;
ancestor=ancestor->left;
}
else
{
ancestor=ancestor->right;
}
}
return successor;
}
}
void Inorder(Node *root)
{
if(root==NULL) return;
Inorder(root->left);
cout<<root->data<<" ";
Inorder(root->right);
}
Node* Insert(Node *root,char data)
{
if(root==NULL)
{
root=new Node();
root->data=data;
root->left=root->right=NULL;
}
else
if(data<=root->data){
root->left=Insert(root->left,data);
}
else
{
root->right = Insert(root->right,data);
}
return root;
}
int main()
{
Node* root=NULL;
root=Insert(root,6);
root=Insert(root,11);
root=Insert(root,4);
root=Insert(root,5);
root=Insert(root,1);
root=Insert(root,11);
cout<<"Traversal : \n";
Inorder(root);
Node* successor=Successor(root,1);
if(successor==NULL)
{
cout<<"No successor found\n";
}
else
{
cout<<"Successor found at "<<successor->data<<"\n";
}
return 0;
}