Largest Number Smaller in BST

In a binary search tree, find the node containing the largest number smaller than the given target number.

If there is no such number, return -2^31.

Assumptions:

• The given root is not null.

• There are no duplicate keys in the binary search tree.

Examples

5

/ \

2 11

/ \

6 14

largest number smaller than 1 is Integer.MIN_VALUE(Java) or INT_MIN(c++)

largest number smaller than 10 is 6

largest number smaller than 6 is 5

Solution: iterative traversal

Iterative rule:

if larger than: check left

if smaller than: update answer, check right

public int largestSmaller(TreeNode root, int target){
    int result = Integer.MIN_VALUE;
    while (root != null){
        if (root.key >= target){
            root = root.left;
        } else {
            result = root.key;
            root = root.right;
        }
    }
    return root;
}

Time Comp: O(logN) one traversal down tree

Space Comp: O(1)