Binary Search Tree

1. Search an element in Tree T:
1)Recursive Method:
TREE-SEARCH(root[T], k){
x = root[T];
if (x == NIL || key[x] == k)
return x;
else{
if (k < key[x])
return TREE-SEARCH(left[x], k);
else
return TREE-SEARCH(right[x], k);
}
}
2)Iterative Method:
ITERATIVE-TREE-SEARCH(root[T], k){
x = root[T];
while (x != NIL && key[x] != k){
if (k < key[x])
x = left[x];
else
x = right[x];
}
return x;
}

2. Find the minimal element in Tree T:
TREE-MINIMUM(root[T]){
x = root[T];
while ( left[x] != NIL)
x = left[x];
return x;
}

3. Find the maximal element in Tree T:
TREE-MAXIMAL(root[T]){
x = root[T];
while (right[x] != NIL)
x = right[x];
return x;
}

4. Find the successor of element x in Tree T:
TREE-SUCCESSOR(x){
if (right[x] != NIL)
return TREE-MINMIAL(right[x]);
else{
y = p[x];
while (y != NIL && x = right[y]){
x = y;
y = p[y];
}
return y;
}
}