In your program$$s main function, be sure to test each of the

additions you make to LinkedBST. After adding some elements

to your binary search tree to test your methods, it can help to draw

the tree out on paper to make sure your methods are working

properly.

$1.$ Add two methods getSmallest and getLargest to LinkedBST. getSmallest should return the smallest element in the tree and getLargest should return the largest element in the tree.

Note: To improve efficiency, both methods should check the least amount of Nodes required to arrive at the answer. In other words, you should not traverse the entire tree to find the smallest and largest elements.

$2.$ We often want to see if a binary search tree is balanced. To do this, by adding a height method to BinaryNode which returns its height. You can calculate this recursively by the following the recursive equation:

The height of a Node is $1+$ the height of its tallest subtree.

The height of None is $0$

After BinaryNode has a height method, add a height method to LinkedBST which returns the height of the entire tree $($i$.$e$.$ simply call height on the root Node and

return its return value$)$

$3.$ A breadth$-$first traversal $($i$.$e$.$ level$-$order traversal$)$ of a tree visits the Nodes in each level from left to right before visiting the next level. Add a method breadth to LinkedBST which prints out a breadth$-$first traversal of the tree. Note: A breadth$-$first

traversal uses a queue! You may use the LinkedQueue class provided on Canvas and you may use the following pseudocode in your implementation:

breadth:

Create a queue

Add root to the queue

Loop until queue is empty:

print Node at front of queue

pop Node from queue

add Node$$s left and right children to queue

$4.$Write a method is$\_$balanced in LinkedBST which determines if the tree is balanced or not. This method should traverse the tree and check to see if any Node is the root of an unbalanced subtree. If you find an unbalanced Node, return False. If the whole tree is traversed and no unbalanced Nodes are found, return True.

Hint: You can reuse some of your code from breadth in this method to traverse the tree. Or if you prefer, you can reuse some of the code from inorder.

BinaryNode.py:

class BinaryNode:

$"""$ Represents a Node in a binary tree $"""$

def $\_\_$init$\_\_($self$,$ data, left$=$None, right$=$None$)$:

$"""$ By default, this Node will not have any children $"""$

self.data $=$ data

self.left $=$ left

self.right $=$ right

Abstractcollection.py

class AbstractCollection:

def $\_\_$init$\_\_($self$,$ source$\_$collection$=$None$)$:

self.$\_$size $=0$

if source$\_$collection:

for item in source$\_$collection:

self.add$($item$)$

def $\_\_$len$\_\_($self$)$:

return self.$\_$size

def is$\_$empty$($self$)$:

return len$($self$)==0$

def $\_\_$add$\_\_($self$,$ other$)$:

result $=$ type$($self$)($self$)$

for item in other:

result.add$($item$)$

return result