# Search in a Binary Search Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/search-in-a-binary-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/search-in-a-binary-search-tree
**Data structures:** Tree, Binary Tree, Binary Search Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/search-in-a-binary-search-tree/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/search-in-a-binary-search-tree/image1.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 <= 107`
* `root` is a binary search tree.
* `1 <= val <= 107`

# Approaches
## Brute-Force Traversal
This approach treats the Binary Search Tree as a regular binary tree and performs a standard traversal (like pre-order) to visit every node. It doesn't leverage the inherent ordering property of a BST.
**Time:** O(N), where N is the number of nodes in the tree. In the worst-case scenario, we might have to visit every node to find the value or determine it's not present. · **Space:** O(H), where H is the height of the tree, due to the recursion call stack. In the worst case of a skewed tree, H can be equal to N, leading to O(N) space complexity.
**Pros:** Simple to understand and implement.; Guaranteed to work for any binary tree, not just a BST.
**Cons:** Inefficient as it does not utilize the properties of a BST.; Visits unnecessary nodes, leading to a slower runtime compared to optimized approaches.
### Explanation
The algorithm starts at the root and recursively explores the entire tree. At each node, it checks if the node's value matches the target value `val`. If a match is found, the node is returned immediately. If the current node is not a match, the search continues in the left subtree, and if not found there, it proceeds to the right subtree. If the entire tree is traversed without finding the value, `null` is returned. This method is exhaustive and guarantees finding the node if it exists, but it's inefficient as it misses the optimization opportunity provided by the BST structure.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        
        // Search in the left subtree
        TreeNode leftResult = searchBST(root.left, val);
        if (leftResult != null) {
            return leftResult;
        }
        
        // If not in the left, search in the right subtree
        return searchBST(root.right, val);
    }
}
```
### Algorithm
- If the current node is `null`, return `null`.
- If the current node's value equals `val`, return the current node.
- Recursively search in the left subtree. If the node is found there, return the result.
- If not found in the left subtree, recursively search in the right subtree and return its result.

## Recursive Search using BST Properties
This approach takes full advantage of the Binary Search Tree property: values in the left subtree are smaller, and values in the right subtree are larger than the current node's value. This allows us to eliminate half of the remaining tree at each step.
**Time:** O(H), where H is the height of the tree. For a balanced BST, H ≈ log(N), making the complexity O(log N). For a skewed tree, H = N, leading to a worst-case complexity of O(N). · **Space:** O(H) due to the recursion call stack. For a balanced BST, this is O(log N). For a skewed tree, it's O(N).
**Pros:** Much more efficient than a brute-force search for balanced trees.; The logic is clean and directly reflects the definition of a BST search.
**Cons:** The space complexity can be O(N) in the worst case of a skewed tree.; Recursive calls can have a slight overhead compared to an iterative solution.
### Explanation
The search starts at the root. We compare the target value `val` with the current node's value.
- If `val` is equal to the node's value, we've found our target and return the node.
- If `val` is less than the node's value, we know the target, if it exists, must be in the left subtree. So, we recursively call the search function on the left child.
- If `val` is greater than the node's value, the target must be in the right subtree. We then recursively call the search function on the right child.
- If we reach a `null` node, it means the value is not in the tree, and we return `null`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}
```
### Algorithm
- If the root is `null` or `root.val` is equal to `val`, return the root.
- If `val` is less than `root.val`, recursively search in the left subtree: `return searchBST(root.left, val)`.
- If `val` is greater than `root.val`, recursively search in the right subtree: `return searchBST(root.right, val)`.

## Iterative Search using BST Properties
This is an iterative version of the optimized BST search. It uses a loop instead of recursion to traverse the tree, which eliminates the recursion call stack overhead and reduces space complexity to a constant.
**Time:** O(H), where H is the height of the tree. Similar to the recursive approach, this is O(log N) for a balanced tree and O(N) for a skewed tree. · **Space:** O(1). This is the main advantage over the recursive approach. We only use a single pointer to traverse the tree, so the space used is constant regardless of the tree's size or structure.
**Pros:** Most efficient in terms of space complexity (O(1)).; Avoids potential stack overflow errors for very deep trees.; Generally faster in practice due to no function call overhead.
**Cons:** The code might be slightly less intuitive for some developers compared to the direct recursive translation of the search logic.
### Explanation
We initialize a pointer, `current`, to the root of the tree. We then enter a loop that continues as long as `current` is not `null`. Inside the loop, we compare `val` with `current.val`.
- If `val` is equal to `current.val`, we've found the node and break the loop.
- If `val` is less than `current.val`, we know the target must be in the left subtree, so we update `current` to `current.left`.
- If `val` is greater than `current.val`, we update `current` to `current.right`.
The loop effectively traverses a single path from the root down towards the potential location of the node. When the loop terminates, `current` will either point to the found node or be `null` if the value doesn't exist in the tree. We then return `current`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode current = root;
        while (current != null && current.val != val) {
            if (val < current.val) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return current;
    }
}
```
### Algorithm
- Initialize a `current` pointer to the `root`.
- Loop as long as `current` is not `null` and `current.val` is not equal to `val`.
- Inside the loop, if `val` is less than `current.val`, update `current` to `current.left`.
- Otherwise (if `val` is greater than `current.val`), update `current` to `current.right`.
- After the loop, return the `current` pointer.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode searchBST ( TreeNode root , int val ) { if ( root == null || root . val == val ) { return root ; } return root . val < val ? searchBST ( root . right , val ) : searchBST ( root . left , val ); } }
```

### Python

```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 : TreeNode , val : int ) -> TreeNode : if root is None or root . val == val : return root return ( self . searchBST ( root . right , val ) if root . val < val else self . searchBST ( root . left , val ) )
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * searchBST ( TreeNode * root , int val ) { if ( ! root || root -> val == val ) return root ; return root -> val < val ? searchBST ( root -> right , val ) : searchBST ( root -> left , val ); } };
```