Pramp Largest Smaller BST Key Problem
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
Solution
public class Node {
private(set) public var value: Int
private(set) public var parent: Node?
private(set) public var left: Node?
private(set) public var right: Node?
public init(_ value: Int) {
self.value = value
}
public func insert(_ value: Int) {
if value < self.value {
if let left = left {
left.insert(value)
} else {
left = Node(value)
left?.parent = self
}
} else {
if let right = right {
right.insert(value)
} else {
right = Node(value)
right?.parent = self
}
}
}
public convenience init(array: [Int]) {
precondition(array.count > 0)
self.init(array.first!)
for v in array.dropFirst() {
insert(v)
}
}
}
func findLargestSmallerKey(rootNode: Node, num: Int, result: Int) -> Int {
var result = result
if rootNode.value < num && rootNode.value > result {
result = rootNode.value
print(result)
}
if rootNode.value > num {
if rootNode.left == nil { return result }
result = findLargestSmallerKey(rootNode: rootNode.left!, num: num, result: result)
} else {
if rootNode.right == nil { return result }
result = findLargestSmallerKey(rootNode: rootNode.right!, num: num, result: result)
}
return result
}
func findLargestSmallerKey(rootNode: Node, num: Int) -> Int {
return findLargestSmallerKey(rootNode: rootNode, num: num, result: -1)
}Time and Space Complexity
The time complexity is \(O(logn) \). Because of the nature of a binary tree, after each recursive call, the problem space is halved.
The space complexity is also \(O(logn) \) because of the stack space used during the recursive calls.
Think Different
- Thought about DFS or BFS as possible solutions before realizing that they weren’t necessary.
- Forgot to include my base case.
- Realized that I needed to overload my function to include the result.
