Question

Java code for a binary tree that does the following:

 Display a menu to the user and request for the desired option.
 Based on the user’s input, request for additional information as follows:
o If the user wants to add a node, request for the name (or ID) of the new node to be added as
well as the name of the desired parent of that node.
 If the parent node already has two children, the new node cannot be added since this
is a binary tree (and each node can only have at most two children).
 Display an appropriate message to the user.
 Display the menu again for the user to make another choice.
 If the parent node already has one child, add the new node as the second child (right
child) of the parent node. Use recursion to traverse the tree to the parent node.
 Display the new tree with the new node added. This should be done using a
recursive method in your project ( method printTree() ).
 Display the menu.
 If the parent node has no children, use recursion to add the new node as the first child
(left child) of the parent node.
 Display the new tree with the new node added.
 Display the menu.

o If the user wants to know the size of the tree (i.e., the number of nodes in the whole tree or a

sub-tree), request for the name or ID of the node that is the root of the desired tree (or sub-
tree). The size of a tree or sub-tree is the number of its children and other ‘descendants’

(including any leaf nodes) plus one (the root node itself).
 Recursively count the number of nodes in the tree (or sub-tree) and display this with
an appropriate message.
 Display the tree (or subtree) whose size was just displayed.
 Display the menu.
o If the user wants to find a node, request for the name or ID of the node to search for in the
tree.
 Search for the node in the tree using recursive calls. If the node is found, display an
appropriate message; otherwise, indicate that the node does not exist in the tree.
 Display the menu.

o If the user wants to exit, terminate the program.
A sample output (to be followed exactly) is included below.

Example Output
A B C
B D E
D H I
H
I
E J K
J
K
C F G
F L
L
G
There are 12 nodes in this tree.
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->.3
Please enter an integer
k
Please enter an integer
6
Invalid input!
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->1
Please input the node you want to add->
M
Please input the parent node of M->
A
Parent already has 2 children.
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->1
Please input the node you want to add->
M
Please input the parent node of M->

F
Node successfully added!
A B C
B D E
D H I
H
I
E J K
J
K
C F G
F L M
L
M
G
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->2
Please input the root node->
A
There are 13 nodes in that tree
A B C
B D E
D H I
H
I
E J K
J
K
C F G
F L M
L
M
G
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->2
Please input the root node->
C
There are 5 nodes in that tree
C F G
F L M
L
M
G
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->3
Please input the node you want to find->

G
Node G found!
G
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->3
Please input the node you want to find->
U
Node U does not exist.
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->0

Design Requirements
The main class (with the main method) in your application should be named BinaryTreeDemo. It is provided in
its entirety below and should not be changed.

public class BinaryTreeDemo {
public static void main(String[] args) {
Controller controller = new Controller();
controller.manipulateTree();
}
}

You should have another class – Controller – whose object is used to call methods to create the initial tree and
then manipulate it depending on the user’s selections from the menu. The constructor for the Controller class
does the following:
 instantiates an object of the TreeDataStructure class (this object is the root of the tree), and
 calls one of the Controller class methods: “createTree()” (given below).
public void createTree() {
root.addChild("B", "A");
root.addChild("C", "A");
root.addChild("D", "B");
root.addChild("E", "B");
root.addChild("F", "C");
root.addChild("G", "C");
root.addChild("H", "D");
root.addChild("I", "D");
root.addChild("J", "E");
root.addChild("K", "E");
root.addChild("L", "F");
root.printTree();
System.out.println("There are " + root.size() + " nodes in this

tree.\n");

}
The Controller class should also have a method (manipulateTree()) which contains the code to loop as long as
the user wants to, and perform the tasks desired by the user. The Controller class should also have a method to
display the menu to the user.

The TreeDataStructure class should implement the ITreeDataStructure interface (which is provided below).
Your TreeDataStructure class should have two constructors: one which accepts only one String parameter (used
to create the root node which has no parent) and a second one which accepts 2 parameters: a String (the ID of
the new node being created, and an ITreeDataStructure object (the parent of this new node). The methods
addChild(), find(), printTree(), and size() in the TreeDataStructure class must be implemented using recursion.

public interface ITreeDataStructure {
/**
* This method checks to see if a node with the parentID exists in the tree.
* If not, it returns false after printing an appropriate message. If the
* node exists, the method checks to see if it already has two children. If
* it does the method returns false. Otherwise, it either adds the new node
* as the parent node’s left child (if the parent has no children) or as the
* right child (if the parent already has one child). A recursive approach is
* used.
*
* @param ID The ID of the new node to be added to the tree.
* @param parentID The ID of the parent of the new node.
* @return true if new node was added successfully, false otherwise.
*/
public boolean addChild(String ID, String parentID);
/**
* This method looks within the tree to find if “value” (the ID of the node
* to be found) is contained in that subtree. As the search progresses down
* the tree different nodes will be calling find().
*
* @param value a string (ID of a node) to be found in the tree
* @return the node, if found.
*/
public ITreeDataStructure find(String value);
/**
* Returns the parent of this node.
*
* @return the parent of this node.
*/
public ITreeDataStructure getParent();
/**
* Returns the size of the tree.
*
* @return the size of the tree (or subtree) starting from this node
* all the way down to the leaf nodes.
*/

public int size();
/**
* Returns a string with the IDs of this node and its immediate children (if
* any) all on one line.
*
* @return a string with the IDs of this node and its immediate children (if
* any).
*/
public String toString();
/**
* Returns the ID of this node.
*
* @return the String ID of this node.
*/
public String getId();
/**
* Uses recursion (and the toString() method) to print (on a line) each
* node's ID and those of any children it has.
*/
public void printTree();
}

Answer 1

PROGRAM :

import java.util.HashMap;
import java.util.Map;
import java.util.*;
interface INode {

public boolean addChild(String ID, String parentID);
public INode find(String value);
public INode getParent();
public int size();
public String toString();
public String getId();
public void printTree();
public void printInInorder();
}
class TreeDataStructure implements INode {

private String data;
private TreeDataStructure left, right, parent;
public TreeDataStructure(){} // no argument constructor

public TreeDataStructure(String data) // one argument constructor
{
this.data = data;
left = right = parent = null;
}

private TreeDataStructure newNode(String data)
{
TreeDataStructure temp = new TreeDataStructure(data);
return temp;
}
@Override
public boolean addChild(String ID, String parentID) {

return addNode(this, ID, parentID);
}
public boolean addNode(TreeDataStructure root, String id, String parentId)
{
if(root==null)
return false;
if(root.data.equals(parentId))
{
if(root.left == null)
{
TreeDataStructure temp = newNode(id);
root.left = temp;
temp.parent = root;
return true;
}
else if (root.right == null)
{
TreeDataStructure temp = newNode(id);
root.right = temp;
temp.parent = root;
return true;
}
else {
System.out.println("Parent already has 2 children.");
return false;
}
}
return addNode(root.left, id, parentId) || addNode(root.right, id, parentId);
}
@Override
public INode find(String value) {
INode node = findNode(this, value);
return node;
}
private TreeDataStructure findNode(TreeDataStructure root, String node)
{
if(root != null){
if(root.data.equals(node)){
return root;
} else {
TreeDataStructure foundNode = findNode(root.left, node);
if(foundNode == null) {
foundNode = findNode(root.right, node);
}
return foundNode;
}
} else {
return null;
}
}
@Override
public INode getParent() {
return this.parent;
}

@Override
public int size() {
return getSize(this);
}

private int getSize(TreeDataStructure node)
{
if(node == null)
return 0;
return getSize(node.left) + getSize(node.right) + 1;
}
@Override
public String getId() {
return this.data;
}

@Override
public void printTree() {
print(this);
}
private void print(TreeDataStructure node) {

if (node == null)
return;
System.out.print(node.data);
if (node.left != null)
System.out.print(node.left.data);
if (node.right != null)
System.out.print(node.right.data);
System.out.println();
this.print(node.left);
this.print(node.right);
}
@Override
public void printInInorder()
{
printInorder(this);
}
public void printInorder(TreeDataStructure root)
{
if(root==null)
return;
System.out.print(root.data);
printInorder(root.left);
printInorder(root.right);
}
}
public class BinaryTree
{
public static void main(String args[])
{
TreeDataStructure root = new TreeDataStructure("A");
root.addChild("B", "A");
root.addChild("C", "A");
root.addChild("D", "B");
root.addChild("E", "B");
root.addChild("F", "C");
root.addChild("G", "C");
root.addChild("H", "D");
root.addChild("I", "D");
root.addChild("J", "E");
root.addChild("K", "E");
root.addChild("L", "F");
root.printTree();
System.out.println("There are " + root.size() + " nodes in this tree.");
int input = 0;
Scanner scanner = new Scanner(System.in);
do {
System.out.println("Please select from one of the following options:");
System.out.println("1. Add Node");
System.out.println("2. Tree Size");
System.out.println("3. Find Node");
System.out.println("0. Exit");
System.out.print("->");
input = scanner.nextInt();

switch (input)
{
case 1:
System.out.println("Please input the node you want to add->");
String id = scanner.next();
System.out.println("Please input the parent node of " + id + "->");
String parentId = scanner.next();
if(root.addChild(id, parentId)) {
System.out.println("Node successfully added!");
root.printTree();
}
break;
case 2:
System.out.println("Please input the root node->");
id = scanner.next();
INode temp = root.find(id);
if(temp != null) {
System.out.println("There are " + temp.size() + " nodes in that tree");
temp.printInInorder();
System.out.println();
}
else
System.out.println("Root node " + id + " not present in the tree!");
break;
case 3:
System.out.println("Please input the node you want to look for->");
id = scanner.next();
if(root.find(id)!=null)
System.out.println("Node " + id + " found!");
else
System.out.println("Node " + id + " does not exist.");
break;
default:
System.out.println("Enter correct input data!!!");
break;
}
}while (input != 0);
}
}