###### tags: `Leetcode` `easy` `tree` `python` `c++`

# 700. Search in a Binary Search Tree

## [題目連結:] https://leetcode.com/problems/search-in-a-binary-search-tree/description/

## 題目:
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```.


#### [圖片來源:] https://leetcode.com/problems/search-in-a-binary-search-tree/description/

## 解題想法:
* 求是否存在val的子樹
* 因為題目為BST，root左子小，右子大
* 遞迴判斷即可

## Python: Recursive

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root:
            return None
        if root.val==val:
            return root
        if root.val>val:
            return self.searchBST(root.left,val)
        return self.searchBST(root.right,val)

## Python: 非遞歸

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root:
            return None
        while root:
            if root.val==val:
                return root
            elif root.val>val:
                root=root.left
            else:
                root=root.right
        return None

## C++: Recursive

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root==nullptr)
            return nullptr;
        if (root->val == val)
            return root;
        else if (root->val > val)
            return searchBST(root->left,val);
        return searchBST(root->right,val);
    }
};

## C++: 非遞迴

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root==nullptr)
            return nullptr;
        while (root){
            if (root->val==val)
                return root;
            else if (root->val>val)
                root=root->left;
            else
                root=root->right;
        }
        return nullptr;
    }
};