1+ // BST to Linked List
2+ #include < iostream>
3+ using namespace std ;
4+
5+ class Node
6+ {
7+ public:
8+ int key;
9+ Node *left;
10+ Node *right;
11+
12+ Node (int key){
13+ this ->key = key;
14+ left = right =NULL ;
15+ }
16+ };
17+
18+ Node*insert (Node * root,int key){
19+ if (root==NULL ){
20+ return new Node (key);
21+ }
22+
23+ // rec case
24+ if (key < root->key ){
25+ root->left =insert (root->left ,key);
26+ }
27+ else {
28+ root->right =insert (root->right ,key);
29+ }
30+ return root;
31+
32+ }
33+
34+
35+
36+ void printInOrder (Node *root){
37+ if (root==NULL ){
38+ return ;
39+ }
40+ // left, root, right
41+ printInOrder (root->left );
42+ cout << root-> key <<" ,"
43+ printInOrder (root->right );
44+ }
45+
46+
47+ // ---------Next Inorder Successor
48+
49+ Node *inorderSucc (Node * root, Node * target){
50+
51+ // If Right Subtree
52+ if (target->right !=NULL ){
53+ Node* temp = target->right ;
54+ while (temp->left !=NULL ){
55+ temp = temp->left ;
56+ }
57+ return temp;
58+ }
59+
60+
61+ // Otherwise
62+ Node * temp = root;
63+ Node * succ =NULL ;
64+
65+ while (temp!=NULL ){
66+
67+ if (temp->key > target->key ){
68+ succ = temp;
69+ temp = temp->left ;
70+ }
71+ else if (temp->key < target->key ){
72+ temp = temp->right ;
73+ }
74+ else {
75+ break ;
76+ }
77+ }
78+ return succ;
79+ }
80+
81+
82+ int main (){
83+
84+ Node * root =NULL ;
85+ root =insert (root,8 );
86+ root =insert (root,3 );
87+ root =insert (root,10 );
88+ root =insert (root,1 );
89+ root =insert (root,6 );
90+ root =insert (root,14 );
91+ root =insert (root,4 );
92+ root =insert (root,7 );
93+ root =insert (root,13 );
94+
95+ // Test our Code
96+ Node* t1 = root->left ->right ->right ;
97+ Node* t2 = root->right ;
98+
99+ cout<<" Inorder succ of 7 is" inorderSucc (root,t1)->key <<endl;
100+ cout<<" Inorder succ of 10 is" inorderSucc (root,t2)->key <<endl;
101+
102+
103+
104+ return 0 ;
105+ }