Binary Tree Implementation in Java

More in The Data Structures series.

After learning how to implement a stack, various types of linked lists, and even a hash map in Java, today we’ll see how we can build our own binary tree in Java. Similar to other data structures that we talked about, we have a Node here as well. It is very similar to the Node in a Double Linked List (DLL), but instead of a previous and a next pointer in DLL, we have a left and a right pointer in a binary tree. This is because a binary tree will have utmost two children, one to the left and the other to the right of the node. Again, similar to other data structures post I’ve written, I’m not going to explain what a binary tree is and how it works. We’ll get right into the implementation. So let’s get started.

The Binary Tree

Before we start with the code, we need to have a reference tree, to understand the code and to validate the output of the code. It’s also much easier to understand the functioning of the tree if we have an example to work with. So, that’s just what we’re going to do. I did the painful task of coming up with an illustrative diagram for this post, and here it is:

This is, by far, the simplest binary tree I could come up with for this example code. We have the root node as 1, its left child as 2, and its right child as 3. We then have a couple of children for both these nodes. In this post, we’re going to look at how we can build this tree in the code, and then do the three popular traversals:

1. Pre order traversal
2. In order traversal
3. Post order traversal

Pre order traversal

In pre order traversal, we “visit” the node before we visit its children. So the order is going to be like this:

Node -> Left child -> Right child

In our example, the result of a pre order traversal is this:

1 2 4 5 3 6 7

In order traversal

As the name suggests, in order traversal is where we keep the natural order of traversal, left to right. So the order is like this:

Left child -> Node -> Right child

In our example, the result of an in order traversal is this:

4 2 5 1 6 3 7

Post order traversal

In post order traversal, the node comes after the children. So we visit the left child first, then the right child, then the node, as follows:

Left child -> Right child -> Node

In our example, the result of a post order traversal is this:

4 5 2 6 7 3 1

In our code, we’ll try to achieve these three types of traversals.

The Code

As usual, we’ll see the Node class first.

public class Node<T> {

    private T data;
    private Node<T> left;
    private Node<T> right;

    public Node() {}

    public Node(T value) { this.data = value; }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }
}

As I mentioned earlier, we have the left and the right pointers here to point to the left child and the right child. We use this Node class as the base of our BinaryTree class. The definition of the binary tree class looks like this:

public class BinaryTree<T> {
    
    private Node<T> rootNode;

    public Node<T> getRootNode() {
        return rootNode;
    }

    public void setRootNode(Node<T> rootNode) {
        this.rootNode = rootNode;
    }

}

We now add the traversal methods. Make sure you remember how each traversal works. For these traversal methods, we are going to use recursion, that is, we’re going to call a method from inside that method itself. We do this because we have to traverse the tree all the way to the bottom in the same order as the tree is represented. So first, let’s look at pre order traversal.

Pre order traversal

public static void traversePreOrder(Node node) {

    System.out.print(node.getData() + " ");

    if (node.getLeft() != null) {
        traversePreOrder(node.getLeft());
    }

    if (node.getRight() != null) {
        traversePreOrder(node.getRight());
    }
}

As you can see, we’re printing the value of the node first, then going to the left node, and finally going to the right now. This way, the current node comes first, hence the pre in pre order traversing. In the first iteration of this function call, we’ll pass the root node as the argument. So the root node is “visited” first, then all the left children of the root nodes are visiting in pre order. The output of this function will be the following:

1 2 4 5 3 6 7

In order traversal

In order traversing, as I already explained, will be in the natural left to right order. The following is the code for this:

public static void traverseInOrder(Node node) {

    if (node.getLeft() != null) {
        traverseInOrder(node.getLeft());
    }

    System.out.print(node.getData() + " ");

    if (node.getRight() != null) {
        traverseInOrder(node.getRight());
    }
}

As can be seen from the code snippet, the left children are visited first, before the node, and then we go to the right children. The output for this is as follows:

4 2 5 1 6 3 7

Post order traversal

Finally, we have post order traversing. In this, the left child is visited first, then the right child, and the node comes in the end. So the name post order. Below is the code snippet for that:

public static void traversePostOrder(Node node) {

    if (node.getLeft() != null) {
        traversePostOrder(node.getLeft());
    }

    if (node.getRight() != null) {
        traversePostOrder(node.getRight());
    }

    System.out.print(node.getData() + " ");
}

We’ll get the following output for post order traversing:

4 5 2 6 7 3 1

The complete BinaryTree class looks like this:

public class BinaryTree<T> {
    
    private Node<T> rootNode;

    public Node<T> getRootNode() {
        return rootNode;
    }

    public void setRootNode(Node<T> rootNode) {
        this.rootNode = rootNode;
    }
    
    public static void traverseInOrder(Node node) {

        if (node.getLeft() != null) {
            traverseInOrder(node.getLeft());
        }

        System.out.print(node.getData() + " ");

        if (node.getRight() != null) {
            traverseInOrder(node.getRight());
        }
    }

    public static void traversePreOrder(Node node) {

        System.out.print(node.getData() + " ");

        if (node.getLeft() != null) {
            traversePreOrder(node.getLeft());
        }

        if (node.getRight() != null) {
            traversePreOrder(node.getRight());
        }
    }

    public static void traversePostOrder(Node node) {

        if (node.getLeft() != null) {
            traversePostOrder(node.getLeft());
        }

        if (node.getRight() != null) {
            traversePostOrder(node.getRight());
        }

        System.out.print(node.getData() + " ");
    }
}

This is a fairly simple example of a binary tree. This gets more interesting as we add more levels to the tree. You can try that by yourself. But how do we test the code that we just wrote? We’ll see that in the next section.

The Testing

In our main class, we’ll create a binary tree of type Integer and add the root node with the code snippet given below:

BinaryTree<Integer> binaryTree = new BinaryTree<>();
Node<Integer> rootNode = new Node<>(1);
binaryTree.setRootNode(rootNode);

Once we have the root node setup, we can start adding children to the root node like this:

binaryTree.getRootNode().setLeft(new Node<>(2));
binaryTree.getRootNode().setRight(new Node<>(3));

Next, we’ll start adding more nodes to these two nodes like this:

binaryTree.getRootNode().getLeft().setLeft(new Node<>(4));
binaryTree.getRootNode().getLeft().setRight(new Node<>(5));

binaryTree.getRootNode().getRight().setLeft(new Node<>(6));
binaryTree.getRootNode().getRight().setRight(new Node<>(7));

This is the complete code to create the binary tree that I have represented in the illustration at the beginning of this post. Now, let’s see how to traverse this tree:

System.out.println("Pre order traversing:");
BinaryTree.traversePreOrder(binaryTree.getRootNode());
System.out.println();

System.out.println("In order traversing:");
BinaryTree.traverseInOrder(binaryTree.getRootNode());
System.out.println();

System.out.println("Post order traversing:");
BinaryTree.traversePostOrder(binaryTree.getRootNode());
System.out.println();

That’s pretty straight forward. The output of this code is as follows:

Pre order traversing:
1 2 4 5 3 6 7 
In order traversing:
4 2 5 1 6 3 7 
Post order traversing:
4 5 2 6 7 3 1 

The traversing is working as we expected it to. So we’re done here.

As usual, I have a complete maven project already setup for this implementation. You can check that out or fork it from my Github repo.

And if you like what you see here, or on my Medium blog, and would like to see more of such helpful technical posts in the future, consider supporting me on Patreon and Github.