Find Largest Smaller BST Key
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.
For example:
For num = 17 and the binary search tree below:
Your function would return:
14 since it’s the largest key in the tree that is still smaller than 17.
Give it a try using the code editor!
Need a refresher on Binary Search Trees? Check out Exponent's lesson on Trees or take this interactive BST visualizer out for a spin.
Some candidates look first for num in the tree, then look for its predecessor. But num isn't necessarily a key — it could be any number.
Can you explain why it's possible to always store the last key smaller than num without comparing it to the previously stored 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).
def find_largest_smaller_key(self, num):
result = -1
currentNode = self.root
while currentNode is not None:
if currentNode.key < num:
result = currentNode.key
currentNode = currentNode.right
else:
currentNode = currentNode.left
return result
Good Question, but I would've marked this as medium not hard difficulty, since it's just a straightforward traversal.