Lecture 27 Objectives

KNOW:

• How to search for an item in a binary search tree
• How to insert an item into a binary search tree
• How to remove an item from a binary search tree
• The best-case and worst-case analyses for searching a binary search tree

BE ABLE TO:

• Draw "before" and "after" pictures of a binary search tree into which a particular value has been inserted
• Draw "before" and "after" pictures of a binary search tree from which a particular value has been removed
• Write a non-recursive function that searches a binary search tree for a given value, and returns true if the value is found in the tree
• Write a recursive function that searches a binary search tree for a given value, and returns true if the value is found in the tree

Sample Exam Question:

Here is a binary search tree:

               root ->    85
                         /  \
                        /    \
                      37      102
                     / \      / \
                   12   76   91  115
                                   \
                                    137

1. Draw a picture of the tree that will result when the value 100 is inserted into the given tree.
2. Starting with the original tree again, draw a picture of the tree that will result when the value 37 is removed from the tree.