Question

Develop a Java application to implement a binary tree data structure. A tree data structure starts from the top node, called the root. Each node in the tree has a set of children, which are also nodes of the tree and can have children of their own, and so on. This keeps on going till we get to the bottom of the tree, to the “leaf” nodes. Each node in the tree, except for the root, has a parent. A binary tree is a specialized form of a tree data structure in which each node in the tree has at most two children.

A binary tree can be represented using the format in the example below. Each line contains at most three characters. The first character is the ID of the node itself. The next two characters are the child nodes. If a line has only 2 characters, then that node has only one child. If a line has one character only, then it is a leaf node (i.e., it has no children). Example

A B C

B D E

C F G

D H I

E J K

F L

G

H

I

J

K

L

The application should exhibit the following functionality (see the sample output provided):

• 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 / 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, use recursion to add the new node as the second child (right child) of the parent node.

• Display the new tree with the new node added. This should be done using a recursive method in your project (printTree() ).
• Display the menu options.

▪  If the parent node has no children, use recursion to add the new node as the left child

of the parent node.

• Display the new tree with the new node added.
• Display the menu options.

o If the user wants to know the size of the tree (i.e., the number of nodes in the tree or sub-tree), request for the name / ID of the node that is the root of the desired tree / 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. For example, the size of the sub-tree with root ‘B’ in Figure 2 above is 7.

▪ Recursively count the number of nodes in the tree / sub-tree and display this with an appropriate message.

• Display the newly updated tree.
• Display the menu options.

o If the user wants to find a node, request for the name / ID of the node to search for in the tree.

▪ Search recursively for the node in the tree; if the node is found, display an appropriate

message, otherwise, indicate that the node does not exist in the tree.

•Display the menu options.

o If the user wants to exit, terminate the program.

A sample output (to be followed exactly) is included below.

Example Output

ABC

BDE

DHI

H

I
EJK
J
K
CFG
FL
L
G
There are 12 nodes in this tree.

Please select from 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->
P
Please input the parent node of P->
A
Parent already has 2 children.
Please select from 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->
P
Please input the parent node of P->
F
Node successfully added!
ABC
BDE
DHI
H
I
EJK
J
K
CFG
FLP

L
P
G
Please select from one of the following options:

1. Add Node

2. Tree Size

3. Find Node

0. Exit

->2

Please input the root node->

F

There are 3 nodes in that tree
FLP
Please select from one of the following options:

1. Add Node
2. Tree Size
3. Find Node
0. Exit
->3
Please input the node you want to look for->
P
Node P found!
P
Please select from one of the following options:

1. Add Node
2. Tree Size
3. Find Node
0. Exit
->3
Please input the node you want to look for->
N
Node N does not exist.
Please select from one of the following options: 1. Add Node
2. Tree Size
3. Find Node
0. Exit
->0

The main class in your application should be named BinaryTree. This class should instantiate an instance of the second class – to be named TreeDataStructure – and that instance should be used to call the appropriate methods to generate the initial tree, display the menu to the user and exhibit the functionality described above. Apart from the main method, the BinaryTree class should also have a method to print the menu options (void printMenu() ). You can copy and paste the code below into your main class to generate the initial tree.

public static void main(String[] args) {

TreeDataStructure root =

root.addChild("B", "A");

root.addChild("C", "A");

root.addChild("D", "B");

root.addChild("E", "B");

new TreeDataStructure("A");

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");

The TreeDataStructure class should implement the INode interface (which is provided below). The methods addChild(), find(), printTree(), and size() in the TreeDataStructure class must be implemented recursively. NOTE: Using recursion is one of the main objectives of this assignment. A solution that does not use recursion to implement the required functionality will earn zero points. Create an interface named INode within your package (following steps similar to how you would create a class) and copy and paste the interface code below into it.

public 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();

Hints

1. It is important to store information about the parent of each node as part of that node’s internal structure. In addition, each node should have information about its’ children.
2. You may represent the children of a node possibly using an array of nodes.

Answer 1

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);
    }
}