# [Programming Problem] Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

• If ‘P’ >= current Node, go right as the next node is in the right sub tree
• If ‘P’ < current Node, go left as the next node is in the left sub tree
• On return of recursion we have a few choices.
1. Both the current node and return value are not a solution (i.e. <= P). Return null
2. If one of the node’s is not a solution (i.e. <= P). Return the other!
3. If both are a solution (i.e. both > P). Calculate the one with the smaller difference to P and return!

Time complexity would be average case O(Log N), worst case O(N).

```/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @param {TreeNode} p * @return {TreeNode} */ var inorderSuccessor = function(root, p) { let ret = inorderSuccessorFunc(root, p); if (ret.val === Number.POSITIVE_INFINITY) return null; else return ret; };   var inorderSuccessorFunc = function(root, p) {   if ( root === null ) return new TreeNode(Number.POSITIVE_INFINITY);   let ret = null; if ( p.val >= root.val ) ret = inorderSuccessorFunc(root.right, p); else ret = inorderSuccessorFunc(root.left, p);   // Answer: no candidate! if ( root.val <= p.val && ret.val <= p.val ) return null;   // Answer: returned value from recursion if ( root.val <= p.val && ret.val > p.val ) return ret;   // Answer: current root value is the answer if ( root.val > p.val && ret.val <= p.val ) return root;   // Answer: Both are potential answers return Math.abs(ret.val-p.val) < Math.abs(root.val-p.val) ? ret : root;   }```