Inorder Successor of a node in Binary Tree | C # 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 Code ; Case 1 ; case 2 ; case 3
using System ; class GFG { public class Node { public int data ; public Node left , right ; } public static Node temp = new Node ( ) ; public static Node newNode ( int data ) { Node temp = new Node ( ) ; temp . data = data ; temp . left = temp . right = null ; return temp ; } public static Node leftMostNode ( Node node ) { while ( node != null && node . left != null ) { node = node . left ; } return node ; } public static Node rightMostNode ( Node node ) { while ( node != null && node . right != null ) { node = node . right ; } return node ; } public 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 ) { Console . Write ( " Inorder ▁ Successor ▁ of ▁ " + x . data ) ; Console . Write ( " ▁ is ▁ " + root . data + " STRNEWLINE " ) ; return null ; } } return root ; } return null ; } public static void inorderSuccesor ( Node root , Node x ) { if ( x . right != null ) { Node inorderSucc = leftMostNode ( x . right ) ; Console . Write ( " Inorder ▁ Successor ▁ of ▁ " + x . data + " ▁ is ▁ " ) ; Console . Write ( inorderSucc . data + " STRNEWLINE " ) ; } if ( x . right == null ) { int f = 0 ; Node rightMost = rightMostNode ( root ) ; if ( rightMost == x ) { Console . Write ( " No ▁ inorder ▁ successor ! ▁ " + " Right ▁ most ▁ node . STRNEWLINE " ) ; } 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 ) ; } }