Reference no: EM13346646

Recursive tree algorithms

Algorithms to Write:

1. Write a recursive function to determine if a binary tree is a binary search tree.  For example, in the trees above, the tree on the left is a binary search tree, while the tree on the right is not.

2. The location of a node in a binary search tree is defined as a string such as LLRRL, which represents the node that you find by starting at the root, and traversing Left, traverse Left, traverse Right, traverse Right, and traverse Left.   Write a function to print a path to some target 'x' based on the direction from the root to the target.  For example, in the tree above, the path from 65 to 52 is LRR. Hint: use a stack to store the path.

3. Write a recursive algorithm to count the number of right children in a binary search tree.

4. Write the method levelCount whose header is given below. Method levelCount returns the number of nodes on the specified level.

int BinarySearchTree<Type> :: levelCount(BinaryNode<Type>* t, int level);

For this problem, the root is at level zero, the root's children are at level one, and for any node N its level is one more than N's parent's level. For example, for the bean-tree diagrammed below, the call levelCount(t,1) should return 2 (chickpea and navy are on level 1); the call levelCount(t,2) should return 3; and the call levelCount(t,4) should return 0.

Hint: when the level is 0, there is always just one node at that level, the root node (assuming it isn't empty), so return 1. If the level isn't zero, recursive calls will be used to determine the number of nodes at the requested level, and the level-requested should change in the recursive calls.

5. Write a recursive algorithm to delete the leaves of a binary tree.

Programming Requirements

You must use the binary search tree code provided.  Each algorithm must be implemented as both a private method and a public method of the class.  Your code will be tested using the program provided.

Other Requirements 

• File names must match exactly to the file names provided
• Clearly state any additional assumptions you may need to make.