Binary Search Tree – Searching, Deletion

Searching a BST is even simpler than insertion. The pseudocode is self-explanatory but we will look brie°y at the premise of the algorithm nonetheless.
We have talked previously about insertion, we go either left or right with the right subtree containing values that are ¸ x where x is the value of the node
we are inserting. When searching the rules are made a little more atomic and at any one time we have four cases to consider:

1. the root = ; in which case value is not in the BST; or
2. root.Value = value in which case value is in the BST; or
3. value < root.Value, we must inspect the left subtree of root for value; or
4. value > root.Value, we must inspect the right subtree of root for value.
1) algorithm Contains(root, value)
2) Pre: root is the root node of the tree, value is what we would like to locate
3) Post: value is either located or not
4) if root = ; 5) return false
6) end if
7) if root.Value = value
8) return true
9) else if value < root.Value
10) return Contains(root.Left, value)
11) else
12) return Contains(root.Right, value)
13) end if
14) end Contains

Deletion

Removing a node from a BST is fairly straightforward, with four cases to consider:

1. the value to remove is a leaf node; or
2. the value to remove has a right subtree, but no left subtree; or
3. the value to remove has a left subtree, but no right subtree; or
4. the value to remove has both a left and right subtree in which case we

promote the largest value in the left subtree.
There is also an implicit ¯fth case whereby the node to be removed is the only node in the tree. This case is already covered by the ¯rst, but should be
noted as a possibility nonetheless. Of course in a BST a value may occur more than once. In such case the ¯rst occurrence of that value in the BST will be removed.

The Remove algorithm given below relies on two further helper algorithms named FindP arent, and FindNode which are described in x3.4 and x3.5 re-
spectively.