Implement function to check if a key exists in a BST recursively and iteratively.
Given a binary search tree, determine whether a target key is present in the tree using both a recursive solution and an iterative solution.
This problem tests the core property of a binary search tree: values in the left subtree are smaller than the root, and values in the right subtree are larger. To search for a key, you do not need to traverse the whole tree; at each node, compare the target with the current value and move left or right accordingly. The recursive solution mirrors that decision naturally, while the iterative solution uses a loop to walk down the tree until the key is found or a null node is reached. The main interview point is using BST ordering correctly and writing an O(h) search, where h is the tree height.
