Find largest smaller key in Binary Search Tree

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

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)O(log⁡N)
time where NN 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.