# Binary search tree: insert

## General Information

Algorithmic problem: Sorted sequence: insert

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$.
2. The Key $K$ is in the range of v.

Variant: $i$ is increased by 1.

Break condition: One of the following two conditions is fulfilled:

1. It is $p$.key $\geq K$ and $p$.left $=$void.
2. It is $p$.key $\leq K$ and $p$.right $=$void.

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: If the tree is empty, a new root with key $K$ is created; otherwise, $p$ is initialized so as to point to the root.

Implementation:

1. If root = void:
1. Create a new binary search tree node and let root point to it.
2. Set root.key$:= K$, root.left $:=$ void, and root.right $:=$ void.
2. Otherwise, set $p := root$.

Proof: Obvious.

## Induction Step

Abstract view: If the direction where to go next is void, insert $K$ in that empty slot and terminate the algorithm. Otherwise, proceed in that direction.

Implementation:

1. If $p$.key $= K$:
1. If $p$.left = void:
1. Create a new node and let $p$.left point to it.
2. Set $p$.left.key $:= K$, $p$.left.left $:=$void, and $p$.left.right $:=$ void.
3. Terminate the algorithm.
2. Otherwise, if $p$.right = void:
1. Create a new node and let $p$.right point to it.
2. Set $p$.right.key $:= K$, $p$.right.left := void, and $p$.right.right := void.
3. Terminate the algorithm.
3. Otherwise, set $p := p$.left.
2. Otherwise, if $p$.key $\gt K$:
1. If $p$.left = void:
1. Create a new node and let $p$.left point to it.
2. Set $p$.left.key $:= K$, $p$.left.left $:=$void, and $p$.left.right $:=$void.
3. Terminate the algorithm.
2. Otherwise, set $p := p$.left.
3. Otherwise (that is, $p$.key $\lt K$):
1. If $p$.right = void:
1. Create a new node and let $p$.right point to it.
2. Set $p$.right.key $:= K$, $p$.right.left $:=$void, and $p$.right.right $:=$void.
3. Terminate the algorithm.
2. Otherwise, set $p := p$.right.

## 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-INSERT(T, z)

y = Null
x = root(T)
while x ≠ NULL
y = x
if key[z] < key[x]
then x = left[x]
then x = right[x]
p[z] = y
if y = NULL
then root[T] = z //Tree was empty
else if key[z] < key[y]
then left[y] = z
else right[y] = z