### 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:

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.

### David Inga

Designed by David Inga in California.