# Binary Search Tree Search

# Binary Search Tree Search

Binary Search Tree (BST) search locates a key by following the tree structure and using the ordering invariant:

* all keys in the left subtree are smaller
* all keys in the right subtree are larger

This property allows you to discard half of the remaining subtree at each step, similar in spirit to binary search on arrays.

## Problem

Given a binary search tree with root node `root` and a target key `x`, find a node such that

$$
node.key = x
$$

If no such node exists, return null.

## Algorithm

Start at the root. At each node:

* if the current key equals the target, return it
* if the target is smaller, move to the left child
* if the target is larger, move to the right child

Continue until you either find the key or reach a null pointer.

```text
bst_search(root, x):
    node = root
    while node != null:
        if x == node.key:
            return node
        else if x < node.key:
            node = node.left
        else:
            node = node.right
    return null
```

## Example

Consider the tree:

```
        8
       / \
      3   10
     / \    \
    1   6    14
```

Search for `6`:

| step | node | comparison | move   |
| ---- | ---- | ---------- | ------ |
| 1    | 8    | 6 < 8      | left   |
| 2    | 3    | 6 > 3      | right  |
| 3    | 6    | equal      | return |

## Correctness

The BST invariant ensures that at any node:

* all possible matches for $x$ must lie entirely in one subtree
* the algorithm always moves into the only subtree that can contain $x$

If the algorithm reaches a null pointer, then no valid position for $x$ exists in the tree.

## Complexity

| case                | time        |
| ------------------- | ----------- |
| balanced tree       | $O(\log n)$ |
| worst case (skewed) | $O(n)$      |

Space complexity:

* iterative version: $O(1)$
* recursive version: $O(h)$ where $h$ is tree height

## When to Use

BST search is useful when:

* you need dynamic ordered data
* insert, delete, and search operations must all be supported
* you want in-order traversal to produce sorted output

For guaranteed logarithmic performance, use balanced variants such as AVL trees or red-black trees.

## Implementation

```python
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def bst_search(root, x):
    node = root
    while node:
        if x == node.key:
            return node
        elif x < node.key:
            node = node.left
        else:
            node = node.right
    return None
```

```go
type Node struct {
	Key   int
	Left  *Node
	Right *Node
}

func BSTSearch(root *Node, x int) *Node {
	node := root
	for node != nil {
		if x == node.Key {
			return node
		} else if x < node.Key {
			node = node.Left
		} else {
			node = node.Right
		}
	}
	return nil
}
```