Problem

Given a root of a Binary Search Tree (BST) and a number num, implement

an efficient function findLargestSmallerKey that finds the largest key

in the tree that is smaller than num. If such a number doesn’t exist,

return -1. Assume that all keys in the tree are nonnegative.

The Bst Class is given to me.

```
public class BstNode
{
public int key;
public BstNode left;
public BstNode right;
public BstNode parent;
public BstNode(int keyt)
{
key = keyt;
}
}
```

you can ignore the unit test code this is a just the demo.

```
[TestMethod]
public void LargestSmallerKeyBstRecrussionTest()
{
BstNode root = new BstNode(20);
var left0 = new BstNode(9);
var left1 = new BstNode(5);
var right1 = new BstNode(12);
right1.left = new BstNode(11);
right1.right = new BstNode(14);
left0.right = right1;
left0.left = left1;
var right0 = new BstNode(25);
root.right = right0;
root.left = left0;
Assert.AreEqual(14, helper.FindLargestSmallerKeyRecursion(17, root));
}
```

this is the code I would like you please to review, comment.

```
public static int FindLargestSmallerKey(uint num, BstNode root)
{
if (root == null)
{
return -1;
}
int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
if (root.key < num)
{
return Math.Max(root.key, temp);
}
return temp;
}
```

Solution

Your code works correctly now (as far as I can tell). But due to

```
int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
```

it always traverses the entire tree. This can be improved:

- If
`root.key < num`

then`root.key`

is a possible candidate for the result,

better candidates can only exist in the right subtree. - Otherwise, if
`root.key >= num`

, keys less than the given bound can only

exist in the left subtree.

That leads to the following implementation:

```
public static int FindLargestSmallerKey(uint num, BstNode root)
{
if (root == null) {
return -1;
} else if (root.key < num) {
int tmp = FindLargestSmallerKey(num, root.right);
return tmp != -1 ? tmp : root.key;
} else {
return FindLargestSmallerKey(num, root.left);
}
}
```

This is faster because at each step, only one subtree is inspected instead of both, so that the time complexity is limited by the *height* of

the tree. If the tree is *balanced* then the result is found in O(logN)

time where N

is the number of nodes.

The same idea can be used for an *iterative* solution:

```
public static int FindLargestSmallerKey(uint num, BstNode root)
{
int result = -1;
while (root != null) {
if (root.key < num) {
// root.key is a candidate, continue in right subtree:
result = root.key;
root = root.right;
} else {
// root.key is not a candidate, continue in left subtree:
root = root.left;
}
}
return result;
}
```

I would also add a more comprehensive set of unit tests. Start with

the simplest trees, for example

```
10 10 10 10
/ /
5 15 5 15
```

and call your function with `num`

from 1 to 20. That would already

have helped to find the flaws in your initial implementation.