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.

Leave a Reply

Come See Me

San Francisco, CA
hello@ingax.com

See My Work