Today, we will practice algorithm with a problem relating to binary search tree, which is, search in binary search tree.

Article Contents

### Problem

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`

.

### Analysis

This is a fairly easy problem. Intuitively, if value of current node is less than target value, we scan for left sub-tree, else value of current node is greater than target value, we scan for right sub-tree; do it until the value of current node equals to target value, then we return current node. If the end of tree is reached and no more node to scan, we return `null`

.

We can solve this by using:

- either DFS to go as deep as possible until target value is found or no more possible node to scan.
- or, BFS with a queue to scan.

### Solution

These two solutions are written in Java.

Using DFS

```
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) return root;
return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val);
}
```

Using BFS

```
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) return root;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// if found
if (node.val == val) return node;
// if left node is available
if (node.val > val && node.left != null) queue.offer(node.left);
// if right node is available
else if (node.val < val && node.right != null) queue.offer(node.right);
}
// target not found
return null;
}
```

Additionally, in BFS approach, notice that we only offer into queue only one node each time, so we can simplify by using just a single extra variable to hold the current node.

```
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) return root;
TreeNode node = root;
while (node != null && node.val != val) {
if (node.val < val) node = node.right;
else if (node.val > val) node = node.left;
}
return node;
}
```