Extract the contents of the zip file $(8$ file contents below$)$

Test your code with the supplied JUnit test cases. They are by no means comprehensive. You can write your own test cases.

Complete all the TODO sections in this source file BSTreeMap.java.

Zip only BSTreeMap.java into a file called hw$5.$zip and submit the zip file on Canvas.

Tips:

$$ You should start with the put$()$ and createBST$()$ methods. No other methods will work unless you can build the tree.

$$ While pseudocode often references Node fields, such as $.$left, $.$right, and $.$parent, you must use the getter and setter methods provided in the Node class. This is necessary for the subsequent assignment to work.

$$ Be sure to set parent references correctly.

$$ iterativeSearch$()$ must be written iteratively. Do not use recursion!

$$ Do the tree traversal and metrics methods toward the end.

$$ Do remove$()$ last.

$$ Pseudocode for some methods is found in Canvas in the file: BST$-$SearchInsertDelete.pdf

$1.$ BSTreeMap.java contains:

import java.util.Iterator;

import java.util.Stack;

$/**$

$*$ Class that implements a binary search tree which implements the MyMap

$*$ interface.

$*$ @version $1\mathrm{.}1\mathrm{.}1$ February $27,2024$

$*/$

public class BSTreeMap, V$>$ implements MyMap $\{$

public static final int PREORDER $=1,$ INORDER $=2,$ POSTORDER $=3$;

protected Node root;

protected int size;

$/**$

$*$ Creates an empty binary search tree map.

$*/$

public BSTreeMap$()\{\}$

$/**$

$*$ Creates a binary search tree map of the given key$-$value pairs.

$*$ @param elements an array of key$-$value pairs

$*/$

public BSTreeMap$($Pair$[]$ elements$)\{$

insertElements$($elements$)$;

$\}$

$/**$

$*$ Creates a binary search tree map of the given key$-$value pairs. If

$*$ sorted is true, a balanced tree will be created. If sorted is false,

$*$ the pairs will be inserted in the order they are received.

$*$ @param elements an array of key$-$value pairs

$*/$

public BSTreeMap$($Pair$[]$ elements, boolean sorted$)\{$

if $(!$sorted$)\{$

insertElements$($elements$)$;

$\}$ else $\{$

root $=$ createBST$($elements$,0,$ elements.length $-1)$;

$\}$

$\}$

$/**$

$*$ Recursively constructs a balanced binary search tree by inserting the

$*$ elements via a divide$-$snd$-$conquer approach. The middle element in the

$*$ array becomes the root. The middle of the left half becomes the root's

$*$ left child. The middle element of the right half becomes the root's right

$*$ child. This process continues until low $>$ high, at which point the

$*$ method returns a null Node.

$*$ @param pairs an array of pairs sorted by key

$*$ @param low the low index of the array of elements

$*$ @param high the high index of the array of elements

$*$ @return the root of the balanced tree of pairs

$*/$

protected Node createBST$($Pair$[]$ pairs, int low, int high$)\{$

$//$ TODO

$\}$

$/**$

$*$ Inserts the pairs into the tree in the order they appear in the given

$*$ array.

$*$ @param pairs the array of pairs to insert

$*/$

protected void insertElements$($Pair$[]$ pairs$)\{$

for $($Pair pair : pairs$)\{$

put$($pair$)$;

$\}$

$\}$

$/**$

$*$ Returns the number of key$-$value mappings in this map.

$*$ @return the number of key$-$value mappings in this map

$*/$

public int size$()\{$

$//$ TODO

$\}$

$/**$

$*$ Returns true if this map contains no key$-$value mappings.

$*$ @return true if this map contains no key$-$value mappings

$*/$

public boolean isEmpty$()\{$

$//$ TODO

$\}$

$/**$

$*$ Returns a String of the key$-$value pairs visited with a preorder

$*$ traversal. Uses a StringBuilder for efficiency.

$*$ @return a String of the key$-$value pairs visited with a preorder

$*$ traversal

$*/$

public String preorder$()\{$

StringBuilder builder $=$ new StringBuilder$()$;

builder.append$("[")$;

preorder$($root$,$ builder, $0)$;

builder.append$("]")$;

return builder.toString$()$;

$\}$

$/**$

$*$ Visits the Nodes of the tree in a preorder traversal. Each Node's

$*$ toString$()$ return value should be appended to the StringBuilder. A $","$

$*$ must appear between each Node's data in the final String.

$*$ @param n the current Node

$*$ @param builder the StringBuilder used to build up the output

$*$ @param nodesVisited the number of nodes visited so far. Useful for

$*$ determining when to append $",".$

$*$ @return the number of nodes visited after each recursive call

$*/$

private int preorder$($Node n$,$ StringBuilder builder,

int nodesVisited$)\{$

$//$ TODO

$\}$

$/**$

$*$ Returns a String of the key$-$value pairs visited with an inorder

$*$ traversal. Uses a StringBuilder for efficiency.

$*$ @return a String of the key$-$value pairs visited with an