Design and Analysis of Algorithms: Binary Search Trees

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key ≤ x.key. If y is a node in the right subtree of x, then y.key ≥ x.key.

(Tree 1)

                
                    Inorder-Tree-Walk(x)
                        if x != NIL
                            Inorder-Tree-Walk(x.left)
                            print x.key
                            Inorder-Tree-Walk(x.right)
                
                

Compare with:

                
                    Postorder-Tree-Walk(x)
                        if x != NIL
                            Postorder-Tree-Walk(x.left)
                            Postorder-Tree-Walk(x.right)
                            print x.key
                
                

We search by starting with the root node. If it's key is equal to the key for which we are searching, we are done: that is the key we want.
On the other hand, if we have a NIL node at hand, we are also done, but have failed to find the key.
Finally, if neither is true, we check the key at hand against the key sought for.

• If k < curr.key, recursively call tree search on curr.left.
• Else recursively call tree search on curr.right.

Example:
Let's search for 4 in the tree above.

• 4 < 8; move left
• 4 > 3; move right
• 4 < 6; move left
• Voila!

To find the minimum, we simply walk down the left side of the tree.
To find the maximum, we simply walk down the right side of the tree.

Let's walk through successor for our tree above.

Imagine we are seeking the successor of 3. The right tree of three is non-empty. So we simply seek the minimum of that tree, which is the leftmost node in the tree, in this case, 4.

On the other hand, take this tree, and start with node 10.

10 has no right child, so its successor must lie further up the tree. But it is the right hand node of its parent, so its parent can't be it. However, at the next move back a generation we move left... and that's the successor!

Let's walk through insert for tree 1 above.

We will insert 5. (When I say "Insert x," you should take that to be shorthand for "Insert a node with key x.")

• 5 < 8, so we move left.
• 5 > 3, so we move right.
• 5 < 6, so we move left.
• 5 > 4, so we move right and insert.

Deletion is by far the most complicated coding of any of these functions. There are four cases (z is the node to delete):

1. z has no left child. (This handles two cases!)
   Action: Replace z by its right child, which might be NIL.
2. z has only a left child.
   Action: Replace z by its left child.
3. z has two children.
   Action: Find z's successor y, which lies in its right sub-tree.
   • If y is z's right child, replace z by y.
   • Otherwise, replace y by its own right child, then replace z by y.

Walk through of delete

Let's walk through deleting 8 in the tree above.

• 8 has two children, so we are in case 4.
• The successor of 8 is 9.
• 9 is not the right child of 8.
• So we replace 9 by 10.
• Then we replace 8 by 9.

The right half of tree 2 now looks like this: