Lyft VO 面试真题解析：BST 中查找键是否存在（递归与迭代）

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.

这道题考察二叉搜索树（BST）的基本性质：左子树所有节点都小于根节点，右子树所有节点都大于根节点。查找某个 key 时，不需要遍历整棵树，只要根据与当前节点值的比较结果决定向左还是向右继续搜索即可。递归写法直接把“在左子树 / 右子树继续查找”表达出来；迭代写法则用 while 循环一路向下移动指针，直到找到目标值或走到空节点。面试中重点是清楚地利用 BST 的有序性，并能写出时间复杂度为 O(h) 的实现，其中 h 是树高。