How to Implement Tree in Java

1. Implement a Tree Using Recursion Method
2. Create a Tree in Java Using Generic Method and ArrayList

In this tutorial, we will see two ways to make a tree structure in Java. A tree structure can be useful in several ways, like creating a directory of folders and file names.

Implement a Tree Using Recursion Method

In this example, we create a binary tree with two children at most, one at the left and another at the right. The root node is the parent of all children nodes. Each node stores a value. Below, we take two classes; one is Node representing a node in the tree, and the other is the JavaTree class that performs operations on the nodes.

The Node class has three variables, first is the value to store in the node that is of int data type. Then we take two variables, for left and right child nodes; both the variables are of Node type. We make a constructor of the Node class and initialize the value from the parameter; the left and right variables are set as null.

In the JavaTree class, we take a variable of type Node and call it root. Then we create a method traverseRecursionTree() that takes a Node as a parameter, and inside the method, we check if the node is null; if it is not, then we call the traverseRecursionTree() method from itself and pass the left part of node. After that, we print the value of the node and again call the method from itself and pass the right node. The process of calling the function from itself is called recursion.

In the main() method, we create an object of javaTree and then initialize all the variables like the root, root’s left child, and right child. We also make a left child of the child of the root. We print the whole tree using javaTree.root that contains all the children.

class Node {
  int value;
  Node left;
  Node right;

  public Node(int value) {
    this.value = value;
    left = null;
    right = null;
  }
}

public class JavaTree {
  Node root;

  public void traverseRecursionTree(Node node) {
    if (node != null) {
      traverseRecursionTree(node.left);
      System.out.print(" " + node.value);
      traverseRecursionTree(node.right);
    }
  }

  public static void main(String[] args) {
    JavaTree javaTree = new JavaTree();

    javaTree.root = new Node(10);
    javaTree.root.left = new Node(6);
    javaTree.root.right = new Node(5);
    javaTree.root.left.left = new Node(3);

    System.out.print("Binary Tree: ");

    javaTree.traverseRecursionTree(javaTree.root);
  }
}

Output:

Binary Tree:  3 6 10 5

Create a Tree in Java Using Generic Method and ArrayList

In the previous method, we were limited to only one type of data as the value in the int nodes. In this program, we use the generic method that allows us to use any data type of our choice. We have a class Node<T>, here <T> tells that we can use any data type as a String. In the class, we declare three variables, first is the root that is of type T, then we have parent of type Node<T> and finally an ArrayList of Node<T> named as children.

In the constructor of Node, we take root of T type and set it to the class variable root. Then we initialize the children ArrayList. Now, to add children in the parent we create a addChild() function that takes a child of type T. In the addChild() function, we create an object of Node<T> - childNode and set its parent’s context as the current class’s context using the this keyword. Next, we take the children ArrayList, add the childNode, and return the childNode.

We have multiple methods in the Node<T> class that we can use to perform operations like the getRoot() method that returns the root, the isRoot() function checks if the current node is a root. We create a getLevel() function that returns the level of the node in the tree. At last, we override a toString() method to return the whole tree if it is not null.

Now we create the Javatree class that has the main() method. We create x and y of Node<String> in the class. Here, we use String as the type. In both the constructors, we pass the root of each tree. We print the root using getRoot() and then we create an object of Node<String> named child1 and call the addChild() method using x object, here we pass the value of child1 as argument. In the block of child1, we create three children of child1 using its object and call addChild().

We use the same process to create another tree with the name child2.

import java.util.ArrayList;

class Node<T> {
  private final T root;
  private Node<T> parent;
  private final ArrayList<Node<T>> children;

  public Node(T root) {
    this.root = root;
    children = new ArrayList<>();
  }

  public Node<T> addChild(T child) {
    Node<T> childNode = new Node<T>(child);
    childNode.parent = this;
    this.children.add(childNode);
    return childNode;
  }

  public T getRoot() {
    return root;
  }

  public boolean isRoot() {
    return parent == null;
  }

  public boolean isLeaf() {
    return children.size() == 0;
  }

  public int getLevel() {
    if (this.isRoot())
      return 0;
    else
      return parent.getLevel() + 1;
  }

  @Override
  public String toString() {
    return root != null ? root.toString() : "null";
  }
}

public class JavaTree {
  public static void main(String[] args) {
    Node<String> x = new Node<String>("parent1");
    Node<String> y = new Node<String>("parent2");

    System.out.println(x.getRoot());

    Node<String> child1 = x.addChild("child1");
    {
      Node<String> innerChild1 = child1.addChild("innerChild1OfChild1");
      Node<String> innerChild2 = child1.addChild("innerChild2OfChild1");
      Node<String> innerChild3 = child1.addChild("innerChild3OfChild1");

      System.out.println("-" + child1);

      System.out.println("--" + innerChild1);
      System.out.println("--" + innerChild2);
      System.out.println("--" + innerChild3);

      System.out.println("Level of child1: " + child1.getLevel());
      System.out.println("Level of innerChild2 in Child1: " + innerChild2.getLevel());
    }

    System.out.println();

    System.out.println(y.getRoot());

    Node<String> child2 = x.addChild("child2");
    {
      Node<String> innerChild1 = child2.addChild("innerChild2OfChild2");
      Node<String> innerChild2 = child2.addChild("innerChild3OfChild2");
      Node<String> innerChild3 = child2.addChild("innerChild4OfChild2");
      {
        Node<String> innerChild4 = innerChild3.addChild("innerChild4OfChild3");
        System.out.println(innerChild4.getLevel());
        System.out.println("\nIs inner Child4 Leaf? " + innerChild4.isLeaf());
      }

      System.out.println("-" + child2);

      System.out.println("--" + innerChild1);
      System.out.println("--" + innerChild2);
      System.out.println("--" + innerChild3);

      System.out.println("Level of child1: " + child2.getLevel());
      System.out.println("Level of innerChild2 in Child2: " + innerChild2.getLevel());
    }
  }
}

Output:

parent1
-child1
--innerChild1OfChild1
--innerChild2OfChild1
--innerChild3OfChild1
Level of child1: 1
Level of innerChild2 in Child1: 2

parent2
3

Is inner Child4 Leaf? true
-child2
--innerChild2OfChild2
--innerChild3OfChild2
--innerChild4OfChild2
Level of child1: 1
Level of innerChild2 in Child2: 2