Tutorial 12: Binary Search Tree

Introduction

This tutorial consists mainly of writing several visitors on binary trees that can be put together to solve the problem of deleting from a binary search tree.  The solution is "object-oriented" in the sense that it does not check for the state of the trees to direct the control flow.  Instead, it lets polymorphism direct all control flows by asking the subtrees of to execute appropriate visitors.

Create a local directory comp212/tutorials/12 for this lab and copy the files in ~/comp212/tutorials/12/. These are the Java (incomplete) source code for you to complete.

Exercises

1. Study and complete the code for MaxTreeFinder and MinTreeFinder.  These two visitors will be needed in the binary search tree deletion algorithm.
   
2. BSTDeleter.nonEmptyCase () passes the host to its left subtree and ask it to help to remove the host's root by executing LeftDeleter.   Study and complete the code for LeftDeleter.
   
3. LeftDeleter.emptyCase () asks the right subtree of the host's parent to help to remove the parent's root by executing RightDelDontAsk.   Study and complete the code for RightDelDontAsk ("Right Delete and Don't Ask left sibling to help!").
   
4. You can now compile and test BSTDeleter.
   
5. This last exercise has nothing to do with the binary search tree.  It is a simple exercise on binary trees in general.  It is about counting the leaf nodes in a binary tree by writing a visitor called LeafCounter using anonymous inner class as helper.  A leaf node is a node whose right and left subtrees are both empty.  Study and complete the code for LeafCounter.