Inorder Successor of a node in Binary Tree | CPP program to find inorder successor of a node ; A Binary Tree Node ; Temporary node for case 2 ; Utility function to create a new tree node ; function to find left most node in a tree ; function to find right most node in a tree ; recursive function to find the Inorder Scuccessor when the right child of node x is NULL ; function to find inorder successor of a node ; Case1 : If right child is not NULL ; Case2 : If right child is NULL ; case3 : If x is the right most node ; Driver program to test above functions ; Case 1 ; case 2 ; case 3
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; Node * temp = new Node ; Node * newNode ( int data ) { Node * temp = new Node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } Node * leftMostNode ( Node * node ) { while ( node != NULL && node -> left != NULL ) node = node -> left ; return node ; } Node * rightMostNode ( Node * node ) { while ( node != NULL && node -> right != NULL ) node = node -> right ; return node ; } Node * findInorderRecursive ( Node * root , Node * x ) { if ( ! root ) return NULL ; if ( root == x || ( temp = findInorderRecursive ( root -> left , x ) ) || ( temp = findInorderRecursive ( root -> right , x ) ) ) { if ( temp ) { if ( root -> left == temp ) { cout << " Inorder ▁ Successor ▁ of ▁ " << x -> data ; cout << " ▁ is ▁ " << root -> data << " STRNEWLINE " ; return NULL ; } } return root ; } return NULL ; } void inorderSuccesor ( Node * root , Node * x ) { if ( x -> right != NULL ) { Node * inorderSucc = leftMostNode ( x -> right ) ; cout << " Inorder ▁ Successor ▁ of ▁ " << x -> data << " ▁ is ▁ " ; cout << inorderSucc -> data << " STRNEWLINE " ; } if ( x -> right == NULL ) { int f = 0 ; Node * rightMost = rightMostNode ( root ) ; if ( rightMost == x ) cout << " No ▁ inorder ▁ successor ! ▁ Right ▁ most ▁ node . STRNEWLINE " ; else findInorderRecursive ( root , x ) ; } } int main ( ) { Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> right = newNode ( 6 ) ; inorderSuccesor ( root , root -> right ) ; inorderSuccesor ( root , root -> left -> left ) ; inorderSuccesor ( root , root -> right -> right ) ; return 0 ; }