> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/04-09-2022-700.-search-in-a-binary-search-tree.md).

# 04/09/2022 700. Search in a Binary Search Tree

700\. Search in a Binary Search Tree

Method: recursion

Base case: if root is null or root.val == val, we return root.

Otherwise, we compare the root.val with the val. If the root.val is > val, we traverse the right subtree, else we traverse the left subtree.

Time O(H)

Space O(H)

```
// Some code
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;
        
        if (root.val > val) return searchBST(root.left, val);
        return searchBST(root.right, val);
    }
}
```

Method: itertation.

while the root is not null and root.val != val, we compare the root.val and val. If the root. val is less than the root,valm we set root = root.left, otherwise we set root = root.right.

Time O(H)

Space O(H)

```
// Some code
class Solution {
    // 迭代，利用二叉搜索树特点，优化，可以不需要栈
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null)
            if (val < root.val) root = root.left;
            else if (val > root.val) root = root.right;
            else return root;
        return null;
    }
}

```