BST traversal

initial

here too I thought once we get to the leftmost node, we should update answer. Thats true but the second if statement should be placed after the inorder traversal of left node FIRST. This is cuz if we have value like 4, which doesnt exist in BST in this diagram, we have to return -1. So if the node is bigger than num, we just return. And since ans is declared as -1, we return ans

sol

def find_largest_smaller_key(root, num):
    ans = -1
    curr = root
    
    while curr:
        if curr.key < num:
            # This node is a candidate! 
            # It's smaller than num, so let's save it.
            ans = curr.key
            # Now, let's see if there's an even LARGER value 
            # that is still smaller than num by going right.
            curr = curr.right
        else:
            # This node is >= num, so it's too big.
            # We must go left to find smaller values.
            curr = curr.left
            
    return ans

complexity

log n for balanced
n for skwede space
n time