# LeetCode: 700. Search in a Binary Search Tree

## 题目¶

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.

For example,

```Given the tree:
4
/ \
2   7
/ \
1   3

And the value to search: 2
You should return this subtree:

2
/ \
1   3
```

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.

## 解法¶

### 利用 BST 特性加速查找¶

1. 如果要查找的值等于当前节点的值，当前节点即为要查找的节点。
2. 如果要查找的值小于当前节点的值，则继续在左侧子节点中进行查找。
3. 如果要查找的值大于当前节点的值，则继续在右侧子节点中进行查找。

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def searchBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
if root is None:
return

if val == root.val:
return root
if val > root.val:
return self.searchBST(root.right, val)
if val < root.val:
return self.searchBST(root.left, val)
```