# LeetCode Solution, Easy, 700. Search in a Binary Search Tree

# [700. Search in a Binary Search Tree](https://leetcode.com/problems/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 1:**

![tree1.jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1649897706749/zJYH7Iceu.jpg)

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

**Example 2:**

![tree2.jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1649897712205/njaOXcbvf.jpg)

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

**Constraints:**

- The number of nodes in the tree is in the range `[1, 5000]`.
- `1 <= Node.val <= 10**7`
- `root` is a binary search tree.
- `1 <= val <= 10**7`

### 題目翻譯

這題的需求很簡單就跟標題一樣，要在二元搜尋數中找出跟參數 `val` 一樣的節點，並且回傳以該節點為根節點的子樹。如果沒有相同值的節點，就回傳 `null`。

## 解法解析

可以看到下面的範例，基本上的解法就可以分為兩種：Recursion 和 Iteration。Iteration 的方式看起來是最好的，在跟 Recursion 差不多的時間複雜度下，有更好的空間複雜度。這邊真的想抱怨 Rust 怎麼取個屬性這麼麻煩，寫起來真煩一長串的。

### 解法範例

#### Go

##### Recursion

```go
/**
 * 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 || root.Val == val {
		return root
	}

	if root.Val > val {
		return searchBST(root.Left, val)
	} else {
		return searchBST(root.Right, val)
	}
}
```

##### Iteration

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
	for root != nil && root.Val != val {
		if root.Val > val {
			root = root.Left
		} else {
			root = root.Right
		}
	}
	return root
}
```

#### JavaScript

##### Recursion

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function (root, val) {
    if (!root || root.val === val) return root;

    return root.val > val
        ? searchBST(root.left, val)
        : searchBST(root.right, val);
};
```

##### Iteration

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function (root, val) {
    while (root && root.val !== val) {
        root = root.val > val ? root.left : root.right;
    }
    return root;
};
```

#### Kotlin

##### Recursion

```kotlin
/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun searchBST(root: TreeNode?, `val`: Int): TreeNode? {
        return when {
            root == null -> null
            root.`val` == `val` -> root
            root.`val` > `val` -> searchBST(root.left, `val`)
            else -> searchBST(root.right, `val`)
        }
    }
}
```

##### Iteration

```kotlin
/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun searchBST(root: TreeNode?, `val`: Int): TreeNode? {
        var cur = root

        while (cur != null && cur.`val` != `val`) {
            if (cur.`val` > `val`) {
                cur = cur.left
            } else {
                cur = cur.right
            }
        }
        return cur
    }
}
```

#### PHP

##### Recursion

```php
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution
{

    /**
     * @param TreeNode $root
     * @param Integer $val
     * @return TreeNode
     */
    function searchBST($root, $val)
    {
        if ($root == null || $root->val == $val) {
            return $root;
        }
        return $root->val > $val ? $this->searchBST($root->left, $val) : $this->searchBST($root->right, $val);
    }
}
```

##### Iteration

```php
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution
{

    /**
     * @param TreeNode $root
     * @param Integer $val
     * @return TreeNode
     */
    function searchBST($root, $val)
    {
        while ($root != null && $root->val != $val) {
            $root = $root->val > $val ? $root->left : $root->right;
        }
        return $root;
    }
}
```

#### Python

##### Recursion

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None or val == root.val:
            return root

        return self.searchBST(root.left, val) if val < root.val \
            else self.searchBST(root.right, val)
```

##### Iteration

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root is not None and root.val != val:
            root = root.left if val < root.val else root.right
        return root
```

#### Rust

##### Recursion

```rust
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn search_bst(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
        if root.is_none() || root.as_ref().unwrap().borrow().val == val {
            return root;
        }

        if root.as_ref().unwrap().borrow().val > val {
            return Self::search_bst(root.as_ref().unwrap().borrow().left.clone(), val);
        } else {
            return Self::search_bst(root.as_ref().unwrap().borrow().right.clone(), val);
        }
    }
}
```

##### Iteration

```rust
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn search_bst(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
        let mut node = root;
        while let Some(rc_node) = node.clone() {
            let cur_node = rc_node.borrow();
            if rc_node.borrow().val == val {
                return Some(rc_node.clone());
            }
            if rc_node.borrow().val > val {
                node = rc_node.borrow().left.clone();
            } else {
                node = rc_node.borrow().right.clone();
            }
        }
        None
    }
}
```

#### Swift

##### Recursion

```swift
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
        if root == nil || root!.val == val {
            return root
        }

        return searchBST(root!.val > val ? root!.left : root!.right, val)
    }
}
```

##### Iteration

```swift
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
        var current = root
        while current != nil && current!.val != val {
            current = current!.val > val ? current!.left : current!.right
        }

        return current
    }
}
```