[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.

[Problem Link]

  • 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;
 
}