Inorder Successor of a node in Binary Tree | Java 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
class Solution { static class Node { int data ; Node left , right ; } static Node temp = new Node ( ) ; static Node newNode ( int data ) { Node temp = new Node ( ) ; temp . data = data ; temp . left = temp . right = null ; return temp ; } static Node leftMostNode ( Node node ) { while ( node != null && node . left != null ) node = node . left ; return node ; } static Node rightMostNode ( Node node ) { while ( node != null && node . right != null ) node = node . right ; return node ; } static Node findInorderRecursive ( Node root , Node x ) { if ( root == null ) return null ; if ( root == x || ( temp = findInorderRecursive ( root . left , x ) ) != null || ( temp = findInorderRecursive ( root . right , x ) ) != null ) { if ( temp != null ) { if ( root . left == temp ) { System . out . print ( " Inorder ▁ Successor ▁ of ▁ " + x . data ) ; System . out . print ( " ▁ is ▁ " + root . data + "NEW_LINE");  return null ; } } return root ; } return null ; } static void inorderSuccesor ( Node root , Node x ) { if ( x . right != null ) { Node inorderSucc = leftMostNode ( x . right ) ; System . out . print ( " Inorder ▁ Successor ▁ of ▁ " + x . data + " ▁ is ▁ " ) ; System . out . print ( inorderSucc . data + "NEW_LINE");  } if ( x . right == null ) { int f = 0 ; Node rightMost = rightMostNode ( root ) ; if ( rightMost == x ) System . out . print ( "No inorder successor! Right most node.NEW_LINE");  else findInorderRecursive ( root , x ) ; } } public static void main ( String args [ ] ) { 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 ) ; } }