Answer Happy

11.1. Create template binary search tree class with this name
BSTFCI
and create node class with name BSTNode
- Implement BSTFCI class ( 5 marks)
- Implement BSTNode class ( 5 marks)
11.2. Add Checking Tree Balance
A Balanced Binary Tree is a tree where the heights of the two child
sub-trees of
any node differ by at most one AND the left subtree is balanced AND
the right
subtree is balanced.
Add method called “isBalance” to BSTFCI this method will check in
the BST is
balanced or not.
- Implement isBalance method ( 5 marks)
- Write five test cases and run them correctly ( 5 marks)
11.3. Tree Comparison
Write a function that decides if a BSTFCI T2 is a subtree of
another BSTFCI T1.
Prototype:
bool isSubTree(BSTFCI* t1, BSTFCI* t2);
Note: You may need to write another function that takes 2 BSTNodes
and
compares their sub-trees.
- Implement isSubTree method ( 5 marks)
- Write five test cases and run them correctly ( 5 marks)
11.4. Print Range
Add a recursive function named printRange in the class BSTFCI that
stores
integers and given a low key value and a high key value, it prints
in sorted order all
records whose key values fall between the two given keys. Function
printRange
should visit as few nodes in the BST as possible. You should NOT
traverse ALL
the tree inorder and print the ones in the range. This will not be
considered a
correct solution. You should do smart traversal to only traverse
the related parts.
- Implement printRange method ( 5 marks)
- Write five test cases and run them correctly ( 5 marks
Problem 11: (40 point) - Tree - 11.1. Create template binary search tree class with this name BSTICI and create node class with name BSTNode Implement BSTECI class ( 5 marks) - Implemcut BSTNode class ( 5 marks) 11.2. Add Checking Tree Balance A Balanced Binary Tree is a tree where the heights of the two child sub-trees of any node differ by at most one AND the left subtree is balanced AND the right subtree is balanced. Add method called "isBalance" to BSTFCI this method will check in the BST is balanced or not - Implement is Balance method ( 5 marks) Wiile five les cases and then buitectly marks) 11.3. Tree Comparison Write a function that decides if a BSTFCI 12 is a subtree of another BSTECI TI a . Prototype: buolisSub TreeBSTFCT 11, BSTECI 12); * , ; Note: You may need to write another function that takes 2 BSTNodles and compares their sub-trees Implement is Sub Tree method (5 marks) - Write five test cases and in them conectly ( 5 marks) 3 2 4 1 5 9 / 3 7 8 8 10 / Tree2 2 4 9 1 11 8 10 Tree1 isSubtree (Treel, Tree2) => true isSubtree (Treel, Tree 3) => false Tree 3 11.4. Print Range Add a recursive function named print Range in the class BSTECT that stores integers and given a low key value and a high key value, it prints in sorted order all records whose key values tall between the two given keys. Function printRange should visit as few nodes in the BST as possible. You should NOT averse ALL the tree inortler and print the ones in the range. This will not be considered a Contect solution. You should do smart traversal to only traverse the related parts - Implement printRange method (5 marks) Write five test cases and run them correctly ( 5 marks) 5 3 7 2 4 1 9 9 / 8 10 1 printRange (3, 6) printRange (8, 15) printRange (6,6) => [3,4,5) => [8,9,10] => []