Java Tree Data Structure

In this tutorial, we would be creating a Tree data structure in Java. Java does not have a built in tree data structure. Let’s start by creating a tree as shown in the below image. The tree has a Root node and a number of children

Java Tree Data Structure
Java Tree Data Structure

Java Tree Implementation

Building Tree

In Java Tree, each node except the root node can have one parent and multiple children. Root node doesn’t have a parent but has children.  We will create a class Node that would represent each node of the tree. Node class has a data attribute which is defined as a generic type. Node class also has the reference to the parent and the List of children.

As we have already made the data structure for the tree, now we will be building the Tree.

  1. Create the Root node. Since the root node has no parent, we set the parent as null.
  2.  Add the first child to the root node. addChild adds the child to the node and also assigns the parent to the added node.
  3. And keep on adding the nodes as shown above

And now let’s look at the complete example that adds the nodes to the tree as shown in the above image.

Traversing a Tree

Now that we have build the tree we would be traversing the tree. So we would be using depth first traversal. Here in the below given diagram that shows the depth first traversal.

Depth first traversal
Depth first traversal

 

Here is the method that traverses the tree and prints the node data.

 

Full example of building the tree and traversing the tree.

Here is the output of the program

Add More Functionality

Finding the root of tree from any node

Let’s add some more functionality to the Tree Node. If we need to find the root from any node, we can do that by introducing the following method in the Node class. Since root is the only node in the tree that has parent as null, we can find the root by looking for a parent that has no parent.

Delete Node in the tree

In a tree, one may need a functionality to delete a node in the tree. So as to delete the node, the children of that node need to be assigned to the parent of the deleted node. And if the deleted node is the root node then a new root node needs to be assigned from the children of the deleted root node. Let us create the methods below

Summary

We created a tree data structure with each node having a reference to its parent. The node could also have other functionalities like we added a function to get to the root node and delete any node in the tree. I hope that you have found this tutorial helpful.

7 thoughts to “Java Tree Data Structure”

  1. Thanks for very well explained article. Why do you return the child in addchild (missing in Node class) and not in addchildren.

    1. Thanks for pointing out the issue with Node class. The addChild returns the Node object as that makes it easier for building the tree

    1. Suppose you have to store the hierarchy of a family in Java. A Person would have a list of children and all the children are also of type Person. And then each of these children could also have children.

    1. So as to be able to search the data in tree, here is the method that you can use to search the data. This is not optimised for performance. It is just a modification of the print method.
      private static Optional> findDataInTree(Node node, T searchQuery) {
      if(node.getData().equals(searchQuery)) {
      return Optional.of(node);
      }
      for(Node
      each : node.getChildren()) {
      System.out.println(each.getData());
      Optional> findDataInTree = findDataInTree(each, searchQuery);
      if(findDataInTree.isPresent()) {
      return findDataInTree;
      }
      }
      return Optional.empty();
      }

      And you use it like below

      public static void main(String[] args) {
      Node root = createTree();
      printTree(root, " ");
      String searchQuery = "node 22";
      Optional> findDataInTree = findDataInTree(root, searchQuery);
      System.out.println("Node with data \""+ searchQuery +"\" found :" +findDataInTree.isPresent());

      }

Leave a Reply