Implementing Tree Traversal Algorithms using Java

Tree Traversal Algorithms are important to retrieve data from a Tree data-structure. Each algorithm has certain benefits. It is important to know all of them so that the correct algorithm can be chosen for the correct situation.

A traversal of a tree is a systematic way of accessing or visiting all positions of the tree. A visit could involve anything from increasing the value of a counter variable to performing some complex calculation.

In an earlier post, we looked at Tree Implementation using Java. We declared all the classes and interfaces required for a tree implementation in a step-by-step manner.

In this post, we will take things further. We will specifically look at Tree Traversal Algorithms and also implement them in our Tree implementation.

Preorder Tree Traversal

In preorder traversal of a tree, the root of the tree is visited first. Then, the subtrees rooted at its children are traversed in a recursive manner.

For example, in the above tree, the preorder traversal will be like:

Book -> Title -> 1 -> 1.1 -> 1.2 -> 2 -> 3 -> 3.1 -> 3.2

The pseudocode for the preorder traversal of subtree is as follows:

Algorithm preorder(p)

• perform the “visit” action for position p -> before recursion
• for each child c in children(p) do
  • preorder(c) -> recursively traverse the tree

Java Implementation Preorder Tree Traversal

Preorder Traversal is one of the Tree Traversal Algorithms applicable to all types of trees. Therefore, it would be beneficial to put it in the AbstractTreeClass.

To realize this traversal algorithm, we provide a public method preorder(). This method returns an Iterable collection of positions of the tree in preorder.

The preorder() method in turn uses a private utility method preorderSubtree(). This allows to parameterize the recursive process with a specific position. We also pass a list to this method that serves as a buffer to store the visited positions.

Below is the implementation of these methods:

public Iterable<Position<E>> preorder(){
        List<Position<E>> snapshot = new ArrayList<>();

        if(!isEmpty()){
            preorderSubtree(root(), snapshot);
        }

        return snapshot;
}

private void preorderSubtree(Position<E> p, List<Position<E>> snapshot){
        snapshot.add(p);
        for(Position<E> c: children(p))
            preorderSubtree(c, snapshot);

}

The overall running time for the preorder traversal of tree is O(n).

Postorder Tree Traversal

Postorder Traveral is another important Tree Traversal Algorithm. This algorithm can also be seen as opposite of preorder traversal. This is because it recursively traverses the subtrees rooted at the children of the root and then, visits the root itself.

In the case of the previous tree, a postorder traversal would look like below:

Title -> 1.1 -> 1.2 -> 1 -> 2 -> 3.1 -> 3.2 -> 3 -> Book

Pseudocode for postorder is as follows:

Algorithm postorder(p)

• for each child c in children(p) do
  • postorder(c)
• perform the visit action for position p

Java Implementation Postorder Tree Traversal

To implement postorder traversal, we implement a similar strategy as preorder traversal. We make a public method called postorder() which calls a private utility method postorderSubtree(). Since postorder traversal is also valid for all types of trees, we add these methods in the AbstractTree class.

Below is the implementation for these methods:

public Iterable<Position<E>> postorder(){
        List<Position<E>> snapshot = new ArrayList<>();

        if(!isEmpty()){
            postorderSubtree(root(), snapshot);
        }

        return snapshot;
}

public void postorderSubtree(Position<E> p, List<Position<E>> snapshot){
        for(Position<E> c: children(p))
            postorderSubtree(c, snapshot);

        snapshot.add(p);
}

The postorder traversal algorithm also runs in O(n) time complexity.

Inorder Tree Traversal

Now, we consider a Tree Traversal Algorithm specifically for binary trees. This algorithm is known as inorder tree traversal.

In an inorder tree traversal, we visit a position between the recursive traversals of its left and right subtrees. In other words, the inorder traversal of a binary tree can be viewed as visiting the nodes of the tree from left to right.

An inorder traversal has several important applications. A simple use case is to represent an arithmetic expression.

The pseudo-code for inorder tree traversal is as follows:

Algorithm inorder(p)

• if p has left child lc then
  • inorder(lc)
• perform the visit for position p
• if p has right child rc then
  • inorder(rc)

Java Implementation Inorder Tree Traversal

To implement inorder tree traversal, we again follow a similar strategy as preorder and postorder. We create a public method inorder() and private utility method inorderSubtree(). Since this type of traversal is only applicable for binary tree, we implement these methods in the AbstractBinaryTree class.

We first check if a position has left subtree. If yes, then we traverse it recursively. Then, we visit the position. Lastly, we check if there is a right subtree and then we traverse it recursively.

public Iterable<Position<E>> inorder(){
        List<Position<E>> snapshot = new ArrayList<>();

        if(!isEmpty())
            inorderSubtree(root(), snapshot);

        return snapshot;
}

private void inorderSubtree(Position<E> p, List<Position<E>> snapshot){

        if(left(p) != null)
            inorderSubtree(left(p), snapshot);

        snapshot.add(p);

        if(right(p) != null)
            inorderSubtree(right(p), snapshot);

}

The above algorithms also runs in O(n) time complexity.

Breadth-First Tree Traversal

Although preorder and postorder are common Tree Traversal Algorithms, there is another approach to traverse a tree. In this approach, we visit all positions at depth d before visiting the positions at depth d + 1. Such an algorithms is known as breadth-first traversal.

For breadth-first traversal, we don’t use recursion. The process itself is not recursive since we are not traversing entire subtrees. Instead, we use a queue to produce a FIFO list for the order in which we visit the positions.

Below is a pseudo-code representation of this algorithm.

Algorithm breadthfirst(p)

• initialize queue Q to contain the root node
• while Q not empty do
  • p = Q.dequeue()
  • visit the position p
  • for each child c in children(p) do
    • Q.enqueue(c)

Java Implementation Breadth-First Traversal

Since breadth-first tree traversal is applicable for all types of trees, we implement the method for the same in our AbstractTree class.

We will use an implementation of Queue to help us with this traversal.

public Iterable<Position<E>> breadthFirst(){
        List<Position<E>> snapshot = new ArrayList<>();

        if(!isEmpty()) {
            Queue<Position<E>> queue = new ConcurrentLinkedQueue<>();
            queue.offer(root());
            while (!queue.isEmpty()) {
                Position<E> p = queue.remove();
                snapshot.add(p);
                for (Position<E> c : children(p))
                    queue.offer(c);
            }
        }
        
        return snapshot;
}

The above implementation runs in O(n) time complexity.

Conclusion

With this we have successfully looked at the major Tree Traversal Algorithms. We also provided implementations of all the traversal algorithms.

The code for this is available on Github.

In case you have any queries, please go ahead and sound off in the comments section below. And happy learning!