4
\$\begingroup\$

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;
    }
\$\endgroup\$
  • \$\begingroup\$ @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! \$\endgroup\$ – Gilad Sep 21 '18 at 9:36
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin R Sep 21 '18 at 10:04
  • \$\begingroup\$ Ok i get it, so I just need to find some more questions like this one. To get the "vision" you have. Thanks \$\endgroup\$ – Gilad Sep 21 '18 at 10:18
6
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ yes I did the iterative way first, but I am having a hard time with converting to recursion. so I tried... \$\endgroup\$ – Gilad Sep 21 '18 at 9:52
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin R Sep 21 '18 at 10:02
  • \$\begingroup\$ Yes. I used max to solve that issue but in general you are right. \$\endgroup\$ – Gilad Sep 21 '18 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.