Find largest smaller key in Binary Search Tree
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 &lt; num then root.key is a possible candidate for the result,
better candidates can only exist in the right subtree.
Otherwise, if root.key &gt;= 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 &lt; 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 &lt; 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.