What is a Binary Tree?

Trees are one of the most fundamental data structures to store data.

Binary tree is defined as a data structure and organized in a binary way, where each node has at most 2 children that typically named as left and right nodes.

In this article we’ll talk about the Tree traversal and its three methods process operation and implement an example using Java.

What is a Tree traversal?

Traversal is a process of visiting nodes of a tree such as Queue, Linked List, Arrays.

There are many ways to do it and we will focus on a depth-first which is a traversal algorithm that searches deeply on each branch before switching to another exploration.

There are three differents orders to traversing a tree:

• InOrder traversal In this strategy we traverse the left subtree first, then the root and finally the right one.

1. Traverse the left sub-tree
2. Traverse the root node
3. Traverse the right sub-tree

• Preorder traversal In this strategy we traverse the root first, then the left sub-tree and finally the right sub-tree.

1. Traverse the root node
2. Traverse the left sub-tree
3. Traverse the right sub-tree

• Postorder traversal In this strategy we traverse the left sub-treet, then the right sub-tree and finally the root node.

1. Traverse the left sub-tree
2. Traverse the right sub-tree
3. Traverse the root node

Hands On

P.S: the focus here is only on tree logic, so feel free to refactor the code and apply good practices.

For this example we’ll use the following tree:

Implementing BinaryTree class

1. To represent our binary integer tree we’ll create a Node class with the following fields:

public class Node {
    private int value;
    private Node right, left;

   // getters, setters
}

1. Next, we’ll create a class that represents our binary tree:

public class BinaryTree {
    private Node root;

    public Node getRoot() {
        return root;
    }

    public BinaryTree() {
        this.root = null;
    }  
}

Implementing add method

Continuing in the BinaryTree class, we’ll create a method that will add the elements in order to represent the design:

public void add(int value) {
        Node node = new Node(value);

        if (root == null) {
            this.root = node;
        } else {
            Node current = this.root;

            while(true) {
                if (node.getValue().compareTo(current.getValue()) < 0) {
                    if (current.getLeft() != null) {
                        current = current.getLeft();
                    } else {
                        current.setLeft(node);
                        break;
                    }
                 } else {
                    if (current.getRight() != null) {
                        current = current.getRight();
                    } else {
                        current.setRight(node);
                        break;
                    }
                }
             }
        }
    }

Note that the logic is very simple, first we check the existence of the node and create the first element as root. After that, just check if the next integer is minor or greater than the current one to know which side (right or left) we’ll include the item.

Implementing the processing methods

Well done, our class is set up. Now we ‘ll implement the traversing order methods.

1. First, the implementation of inOrder:

    public void inOrder(Node current) {
        if (current != null) {
            inOrder(current.getLeft());
            System.out.println(current.getValue());
            inOrder(current.getRight());
        }
    }

As explained earlier, in this strategy we traverse the entire tree to the left, then print the root and finally the entire tree to the right. Notice that we are using recursion in this step.

1. Now, the implementation of preOrder:

 public void preOrder(Node current) {
        if (current != null) {
            System.out.println(current.getValue());
            preOrder(current.getLeft());
            preOrder(current.getRight());
        }
    }

Notice that the implementation is basically the same, just changing the order -> Root, left and right.

1. And finally, the postOrder:

public void postOrder(Node current) {
        if (current != null) {
            postOrder(current.getLeft());
            postOrder(current.getRight());
            System.out.println(current.getValue());
        }
    }

In this last strategy, we change the order again -> Left, Right and Root.

Running our Application

All ready 🤩 !! Our binary tree and its methods are implemented. Now, just call our methods passing the values ​​according to our exemplary tree. For this, let’s create a Main class, set the values ​​and print them:

    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();
        tree.add(12);
        tree.add(4);
        tree.add(8);
        tree.add(2);
        tree.add(6);
        tree.add(16);

        System.out.println("#printing inOrder#\n");
        tree.inOrder(tree.getRoot());

        System.out.println("\n#printing preOrder#\n");
        tree.preOrder(tree.getRoot());

        System.out.println("\n#printing postOrder#\n");
        tree.postOrder(tree.getRoot());
    }

After run our application we’ll see the result:

Conclusion

This was a simple example of how to work with a binary tree in java and use traversal processing methods. Feel free to suggest changes or contribute to the project.

You can find the complete source code for this example on my gitHub.

Thanks ❤️