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.
- Both the current node and return value are not a solution (i.e. <= P). Return null
- If one of the node’s is not a solution (i.e. <= P). Return the other!
- 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; } |