Discrete Mathematics for Computer Science

Rooted Trees 383

INPUT: Binary search tree T with root R and an element item

of the type stored at the vertices of T

OUTPUT: TRUE if item is stored in T and FALSE if not

BinSrchTree(R, item) /* Begin the search at root R of T */

BinSrchTree(v, item) /* The recursive procedure */

if(v = 0) then

return FALSE

else

if (item equals the element stored at v) then

return TRUE

else

if item is less than the element at v then

BinSrchTree(item, left child of v)

else

if item is greater than the element at v then

BinSrchTree(item, right child of v)

As an example of the use of this algorithm, we will show how zebra is found on the
binary search tree shown in Figure 6.46.

llama

elephant ga

moose zebra

aardvark gnu horse

Compare zebra with llama

Continue search in light subtree with root ostrich

ostrich

moose zebra

Compare zebra with ostrich

Continue search in light subtree with root zebra

0

zebra

Compare zebra with zebra

Figure 6.46 Search using a binary search tree. SUCCESS!