$2016$ MSISS Q

QUESTION $3$

PARTA:

The following class represents nodes of a binary tree, which stores String objects.

public class Node $\{$

public String key; public Node left; public Node right;

$|$ Node$($String key, Node left, Node right$)\{$

this.key $=$ key; this.left $=$ left; this.right $=$ right;

i$3$

A binary tree is either empty $($represented as a null reference$),$ or it has a root which

is a Node object, whose left and right fields point to two disjoint binary trees.

The following method prints by level all the keys in a binary tree.

public void printByLevel$($Node rcot$)$

The argument of the method is the root of the tree. The output of the method should

contain the keys of the tree, by level. This means that it first prints the root $($Level $1),$

then the keys in children nodes of the root $($Level $2),$ then all keys in children of

children of the root $($Level $3),$ etc.

The relative order of keys within each level is not important. Whitespace and

separators between keys are also not important. You may assume that all strings in

the tree are not null.

Examples:

Output: $$ABCDEFGHIJ$$to be or not to be $$

Implement the above method in Java so it has the most efficient worst$-$case

asymptotic running time. You should justify your answer.

You can use any of the standard generic Abstract Data Types $($ADTs$)$:

Where Comparable is the following generic Java interface:

int compareTo$($T o$)$ Compares this object with the specified object o$.$ It returns

a negative number if $$this is less than o$,$ a positive number

if $$this is greater than o$,$ and zero if $$this is equal to $0.$

You do not need to implement the ADTs you use, but for each one you use you

should specify:

$*$ An AP of the ADT, containing the methods you use in your implementation.

$*$ Atight upper bound of the worst$-$case asymptotic running time of each of the

ADT methods.

$*$ The name of a known implementation of the ADT that has the running time

properties you specified above.