Find the Largest Smaller BST Key

While the code to solve this question is pretty simple, it takes some understanding of binary search trees. There are two key parts for the algorithm.

Part 1: Traversing the tree

A node in a binary search tree is larger than all keys in its left subtree and smaller than all keys i its right subtree. Starting from the root, for each node we choose its left or its right child as the next step, based on a comparison between that node's key and num: If the current node holds a key smaller than num, we proceed to its right subtree looking for larger keys. Otherwise, we proceed to its left subtree looking for smaller keys.

Part 2: Finding the key

During this iteration, when the current key is smaller than num, we store it as our result and keep looking for a larger key that is still smaller than num.

It's important to understand why we always store the last key without comparing it to the value stored beforehand. If we have stored a key before, then it means we have chosen to continue down the key’s right subtree. Therefore, all subsequent keys will be larger than any previously stored keys.

Pseudocode:

function findLargestSmallerKey(rootNode, num):
    result = -1

    while (rootNode != null):
        if (rootNode.key < num):
            result = rootNode.key
            rootNode = rootNode.right
        else:
            rootNode = rootNode.left

    return result

Time Complexity: We scan the tree once from the root to the the leaves and do a constant number of actions for each node. if the tree is balanced the complexity is O(log(N)). Otherwise, it could be up to O(N).

Space Complexity: Throughout the entire algorithm we used only a constant amount of space, hence the space complexity is O(1).