# Binary Search Tree Algorithm

procedure insertion($T$ : binary search tree, $x$: item)
$v:=$ root of $T$
{a vertex not present in $T$ has the value null }
while $v\neq null$ and $label(v) \neq x$
if $x < label(v)$ then
if left child of $v\neq null$ then $v:=$ left child of $v$
else add new vertex as a left child of $v$ and set $v := null$
else
if right child of $v\neq null$ then $v:=$ right child of $v$
else add new vertex as a right child of $v$ and set $v := null$
if root of $T =null$ then add a vertex $v$ to the tree and label it with $x$
else if $v$ is null or $label(v) \neq x$ then label new vertex with $x$ and let $v$ be this new vertex
return $v$ {$v$ = location of $x$}

This entry was posted in Uncategorized. Bookmark the permalink.