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.

T Tak

Hey ! I'm Tak. I'm a software developer since 2008 and been programming since I was 17 years, started with pascal. I love programming, teaching and building stuff on web.

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

      }

  2. Actually, very cleeaaaaar explanation, but why did not you separate the node implementation from the Tree implementation, That woul be much better. Again thank you for the very good explanation 🙂

    1. Thanks for your comments. I omitted the Tree Class as I find that serving no purpose other than holding the root Node. You can add all the methods to the Node class that would be needed for performing any operation on the tree.

  3. How would you remove all the leaf nodes of this tree? I need to remove all the nodes that don’t have children. Thanks for helping

    1. Here is a simple implementation to delete all the leaf nodes under a node. I have also posted the code here https://github.com/t-tak/javagists/tree/master/simple-java-tree

  4. I don’t understand why would you have Node node112 = node11.addChild(new Node(“node 112”)); , node 111 is a child of 11 and 112 is child of 111, so it is already implied logically that 112 is a child (or grandchild) of 11 without explicitly saying that 112 is a child (or grandchild) of 11? or am I wrong?

    1. If you look at the diagram here. You would see that 111 is child of 11 and 112 is also child of 11. As it is child of 11, we add it to 11.
      According to the naming convention i followed in this tutorial, if 111 had 2 children, their names would be 1111 and 1112.

  5. Great article, thank you so much! Could you please tell me what would be the most efficient way to check if a node already exists anywhere in the structure? For example by name if we assume that node data is a String.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.