> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/tree-traversal/largest-number-smaller-in-bst.md).

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