inorder_Successor_bst.java

class Node{
	int data;
	Node left,right;
	Node(int d){
		data=d;
		left=right=null;
	}
}

class Solution
{
    public Node inorderSuccessor(Node root, Node x) {
    Node successorNode = null;
    if (x.right != null) {
      successorNode = minNodeOnLeft(x.right);
    } else {
      successorNode = minNodeOnRightNull(root, x, root.data > x.data ? root : x);
    }
    return successorNode.data == x.data ? null : successorNode;
  }
  Node minNodeOnRightNull(Node node, Node search, Node max) {
    if (node.data == search.data) {
      return max;
    }
    if (search.data < node.data) max = node;
    return search.data < node.data
        ? minNodeOnRightNull(node.left, search, max)
        : minNodeOnRightNull(node.right, search, max);
  }

  Node minNodeOnLeft(Node node) {
   if (node == null) {
      return null;
    }
    Node minNode = minNodeOnLeft(node.left);
    return minNode == null ? node : minNode;
  }
}