Locate the largest key in the BST that is smaller.

This task pertains to Binary Search Trees (BST). A BST is a tree data structure in which each node contains a key, and it has the following properties for any node: All child nodes in the left subtree possess keys that are less than the key of the node. All child nodes in the right subtree possess keys that are greater than the key of the node. When instructed to "Find the Largest Smaller BST Key," you are required to identify the largest key within the BST that is still less than a specified number 'num'.

A method to address this issue involves a variation of Binary Search: Begin at the root and set the result to -1. If the key of the root is greater than or equal to the target number 'num', proceed to the left child of the root node. If the root key is less than 'num': Update the result with the key of the root. Then, move to the right child of the root node. Stop and return the result when you encounter a null node. Here’s an example in Python: class Node : def __init__ ( self , key ) : self . key = key self . left = None self . right = None def findLargestSmallerKey ( root , num ) : result = - 1 while ( root != None ) : if ( root . key < num ) : result = root . key root = root . right else : root = root . left return result In this example, the findLargestSmallerKey function identifies the largest key that is smaller than the specified number 'num' using a while loop. When root.key is less than num, it indicates that a smaller key has been found, so it is updated as the result, and the search continues to the right for a potentially larger key that is still less than num. If root.key is greater than or equal to num, the search shifts to the left to locate a smaller key.

As an alternative, you can approach this problem using recursion. The underlying logic is unchanged; instead of employing a while loop, you will invoke the function on the child nodes. Below is an example in Python: class Node : def __init__ ( self , key ) : self . key = key self . left = None self . right = None def findLargestSmallerKey ( root , num ) : if root is None : return - 1 if root . key < num : r = findLargestSmallerKey ( root . right , num ) return root . key if r == - 1 else r else : return findLargestSmallerKey ( root . left , num ) In this example, the findLargestSmallerKey function searches recursively on the right if the root.key is smaller; otherwise, it searches on the left. The result is passed back up through the recursive call stack after reaching the base case (when root is None).