What is a Binary Tree?

Discover more on YouTube: If you’re looking for video content on technology, programming, and other topics, check out my YouTube channel! Subscribe to stay updated and learn more about these subjects.

Trees are one of the most fundamental data structures for storing data. A binary tree is defined as a data structure organized in a binary way, where each node has at most two children typically named the left and right nodes.

In this article, we will discuss tree traversal and its three methods for process operation, and provide an example implemented using Java

What is a Tree traversal?

Traversal is a process of visiting nodes of a tree such as Queue, Linked List, and 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 different 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-tree, 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
}

2. 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.

2. 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.

3. 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 running our application we’ll see the result:

Conclusion

This is a simple example of how to work with a binary tree in Java and use traversal processing methods. Please feel free to suggest any changes or contribute to the project.

The complete source code for this example can be found on my GitHub page. Thank you! ❤️