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.