LeetCode’s challenge of the day on June 15, 2020 (#700) asks us to search a **Binary Search Tree** and return the node where node.val equals the target value.

To understand why the search in a **Binary Search Tree** (BST) is so **highly efficient**, we first need to understand the **characteristics** of it. A **BST** consists of nodes that each contain either **one**, **two,** or **zero** children. A node that contains zero children is called a **Leaf**.

Each node's left child's value is smaller than the node's value, and the right node's value is larger than the node's value. The nodes on the left are smaller than the nodes on the right.

This means that if we're searching for `target: Int = 70`

on a BST with `root.value = 50`

, we know that the range of the right side of the tree is `range(50, Int.max)`

and therefore we can eliminate the whole left side of the tree. Once we dig further into the tree, we can eliminate huge chunks until we find the node or leaf that is `70`

, or, when we've found that the value doesn't exist.

If `node.val != target`

, while also `node.left > target`

&& `node.right < target`

, then we know that the** target doesn't exist** in the Binary Search Tree.

```
func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
/**
Without a root, nothing to find.
This is the exist condition of our recursion.
*/
guard let node = root else {
return nil
}
/**
First we need to check if the
node.val is the target value.
*/
if node.val == val {
return node
/**
Next we need to check if the target value is larger
or smaller than node's.val...
*/
} else if node.val > val {
// ... and continue down the recursion ...
return searchBST(node.left, val)
} else {
// ... and pass the proper sub tree.
return searchBST(node.right, val)
}
}
```

### Binary Search

The explained characteristics of a Binary Search Tree make searching it so highly efficient. The time complexity is `O(log n)`

because with every iteration, we're able to cut the work load in half (because we're fully eliminating one side of the sub tree).

Due to the nature of how data in a BST is stored, the search is logically the same approach as **binary searching** an array–and equally as efficient.