Largest Smaller BST Key

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.

Analyze the time and space complexities of your solution.

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.

Constraints:

• [time limit] 5000ms
• [input] Node rootNode
• [output] integer

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.

Solution:

##########################################################
# CODE INSTRUCTIONS:                                     #
# 1) The method findLargestSmallerKey you're asked       #
#    to implement is located at line 30.                 #
# 2) Use the helper code below to implement it.          #
# 3) In a nutshell, the helper code allows you to…