# Binary search tree: find

## General Information

Algorithmic Problem: Sorted Sequence:find

Type of algorithm: loop

Auxiliary data: A pointer $p$ of type "pointer to binary search tree node of type $\mathcal{K}$."

## Abstract view

Invariant: After $i\geq 0$ Iterations.

1. The pointer $p$ points to a tree node $v$ on height level $i$ (or is void).
2. The key $K$ is in the range of $v$.

Variant: $i$ is increased by 1.

Break condition: Either it is $p =$void or, otherwise, it is $p$.key $= K$.

Remark: For example, the height of the subtree rooted at the node to which $p$ points may be chosen as the induction parameter. For conciseness, the induction parameter is omitted in the following.

## Induction basis

Abstract view: Set $p:=$ root.

Implementation: Obvious

Proof: Nothing to show

## Induction step

Abstract view: If $p$ points to a node but not with key $K$, $p$ descends in the appropriate direction, left or right.

Implementation:

1. If $p =$ void, terminate the algorithm and return false.
2. Otherwise, if $p$.key $= K$, terminate the algorithm and return true.
3. Otherwise:
1. If $K \lt p$.key, set $p :=$left.
2. If $K \gt p$.key, set $p :=$ right.

Correctness: Obvious.

## Complexity

Statement: The complexity is in $\mathcal{O}(T\cdot h)\subseteq\mathcal{O}(T\cdot n)$ in the worst case, where $n$ is the length of the sequence, $h$ the height of the tree, and $T$ the complexity of the comparison.

Proof: Obvious.

## Pseudocode

TREE-SEARCH (x, k)

if x= NIL or k = key[x]
then return x
if k < key[x]
then return TREE-SEARCH(left[x], k)
else return TREE-SEARCH(right[x], k)