# 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**

&#x20;   5

&#x20; /    \\

2      11

&#x20;    /    \\

&#x20;   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)&#x20;
