Contents

# 700. Search in a Binary Search Tree

## 題目 :

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

### Example :

Note

Example 1:

Input: root = [4,2,7,1,3], val = 2 Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5 Output: []

#### 解題思路 :

• 這題非常簡單，只是要考察你知不知道BST(Binary Search Tree)是什麼!
• Definition of BST : 一個binary tree 由一個root，一個left subtree和一個right subtree組成，其中left subtree中所有的node都小於它的root，而它的right subtree中所有的node都大於它的root，然後每一個subtree都符合BST。

### Recursive解法

• time complexity: O(log(n)) , space complexity: O(1)

Runtime: 20 ms, faster than 93.06% of Go online submissions for Search in a Binary Search Tree.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func searchBST(root *TreeNode, val int) *TreeNode { if root == nil { return nil } if root.Val == val { return root }else if root.Val > val { return searchBST(root.Left, val) } return searchBST(root.Right, val) } ``````