n 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, it can be helpful to add a method to BinaryNode

which calculates its height in the tree. For example, the

height of the Node containing $$Jared$$ in the following tree

is $3,$ the height of the Node containing $$Megan$$ is $2,$ and

the height of the Node containing $$Jim$$ is $1$:

Add a height method to BinaryNode which returns its

height. You can calculate this recursively by the following

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. A breadth$-$first traversal of the

following tree is A$,$ B$,$ C$,$ D$,$ E$,$ F$,$ G:

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.$ If a binary search tree is unbalanced, we may want to

rebalance it to improve the efficiency of the find method.

A tree is unbalanced if any of its Nodes have a left and right

subtree that differ in height by more than $1.$

The following tree is unbalanced because $50$ has a left

subtree of height $1$ and a right subtree of height $3$:

The following tree is unbalanced because $5$ has a left

subtree of height $0$ and a right subtree of height $2$:

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