COSC 2436 Python Programming Assignment 3
1
Derived Binary Search Tree
Specification:
In this assignment, we are creating a subclass of binary search tree to add more helper functions. Those
functions are detailed below. The parent class is BST which is attached with this assignment.
Class Name: Derived_BST
Members in the Derived_BST class
Data fields Data type Purpose
-inherited from BST class
Constructor Purpose
__init__ Parameter list: (self)
call super class’s __init__()
Method Name Return
type
Parameter list
is_leaf bool (self, node)
eturn True if the node passed in is a leaf node, False
otherwise
is_
anch bool (self, node)
eturn True if the node passed is a
anch, False otherwise
parent_node TreeNode (self, value)
eturn the parent node of the node with the value passed in
total_leaf_nodes int (self, node)
eturn total leaf nodes, use recursive algorithm
total_leaf_nodes_iterative int (self)
eturn total leaf nodes, use iterative algorithm
total_nonleaf_nodes int (self)
eturn total non-leaf nodes
get_max int (self)
eturn the maximum value from the tree
get_min int (self)
eturn the minimum value from the tree
eadth_first None (self)
Breadth-First Traversal – use iterative algorithm
Traverse the tree level by level and display the nodes by level
Assignment Instructions:
1. Create a python module to store Derived_BST class
2. Create a python file which contains the main function to test your classes and name it
assignment3_yourFirstName_yourLastName.py
3. To test your code, use the following input value
[12,5,46,80,30,2,56,25,10], you will insert a node 37 in the test program.
4. You can create extra functions to enhance your program
5. Name your variables clearly
COSC 2436 Python Programming Assignment 3
2
6. Add comments to document your project and code
7. Add doc string to document your module/functions
8. Submit two python files and a screen shot of your output in Canvas for grading
Program Output:
Max value: 80
Min value: 2
New node 37 has been added to the tree.
37 is a leaf node?: True
37 is a
anch?: False
30 is the parent node of 37
Total leaf nodes: 5
Total non-leaf nodes: 5
Breadth-First Traversal:
12
5 46
XXXXXXXXXX
XXXXXXXXXX