Find largest smaller key in Binary Search Tree

Question

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

• Gilad: @MartinR Hey I changed the code and fixed the issues I had, I seem to have a hard time with those type of questions. can you please explain how do you look at those type of questions? how do you find all of the edge cases? thanks!
• Martin R: The first problem was "obvious," you handled only the cases where both subtrees are null, or none of them. – Then your initial solution "looked too symmetric" and I just played with the most simple examples.
• Gilad: Ok i get it, so I just need to find some more questions like this one. To get the "vision" you have. Thanks

Answer 1

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(\log N) \$ 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.

• Gilad: yes I did the iterative way first, but I am having a hard time with converting to recursion. so I tried...
• Martin R: @Gilad: I have rewritten the recursive solution slightly, so that it resembles the iterative version more closely. The Math.Max is not needed, since search in right subtree either returns a better result, or -1.
• Gilad: Yes. I used max to solve that issue but in general you are right.