Recursive tree algorithms

Assignment Help Data Structure & Algorithms
Reference no: EM13538

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.

1889_Recursive tree algorithms.png              1562_Recursive tree algorithms1.png

120_Recursive tree algorithms2.png

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.

2176_Recursive tree algorithms3.png

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.

Reference no: EM13538

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

  Use a search tree to find the solution

Explain how will use a search tree to find the solution.

  Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd