Given a Binary Search Tree with parent pointers, write a program to find the in-order successor node of any given node k in that tree.

Problem Note

• Inorder successor of a node is the next node in Inorder traversal of the Binary Search Tree. Inorder Successor is NULL for the last node in In-order traversal.
• In BST, Inorder Successor of an input node can also be defined as the node with the smallest key greater than the key of input node . So, it is sometimes important to find next node in sorted order.

For Example

Input: Given BST is below
           18         
          /  \       
         8    22
        / \
       4   12
           / \
          11  14
k = 14
Output: 18
Explanation: In-order successor of 14 is 18.