## 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.