Lecture 20 Objectives

At the end of today's class you should

KNOW:

the definition for a binary tree
the three common traversal methods for binary trees
the definition for a binary search tree
why the binary search tree is a useful data structure
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

BE ABLE TO:

List the order in which nodes will be visited in a binary tree using preorder, inorder, and postorder traversals
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

Sample Exam Question:

A binary tree contains these values:

           root->    15
                    /  \
                  23    16
                   \    / \
                    9  17  63
                      /     \
                     5       12
                      \
                       37

List the order in which the nodes would be visited if the tree was traversed using a postorder traversal.