Preorder Traversal

The preorder traversal method

Preorder tree traversal is very useful and efficient for copying tree-like data structures. To perform preorder tree traversal, we use a method like preOrder() that will take the node object as a parameter and call itself.

Iterative preorder traversal

Let’s look at an iterative preorder tree traversal code snippet, which will give us a clear picture of how we can implement our algorithm. This shows how we can traverse the tree without recursion.

We start spanning the tree with the root node; after that, we visit the left subtree, and next, we visit the right subtree. Each subtree is also visited in the preorder way. That means it starts from the root of the subtree and then goes to the left subtree, and the process continues until we reach a leaf node.

The traversal pattern clearly tells us that this tree traversal is a good candidate for recursion. After visiting the root node, we can recursively visit the left subtree and then visit the right subtree again.

Still, recursion is not the only way. We can also do the traversal using iteration. The following code snippet shows how:

We get the following output when we run the code above:

A B C D E F 

For implementing a binary tree, we start by making the class for a tree node, TreeNodeClass, which is pretty similar to the node class we made for linked lists. This class has a string attribute, data. Because it’s a binary tree, we have two member nodes for the left and right subnodes (initialized as null in the constructor). Finally, we check whether a node is a terminal node (i.e., a leaf).

Having set up the node class, we can now build the tree from the root node by simply assigning nodes to either the left or right subtree and so on.

Similarly, we can traverse it (nonrecursively) using a stack, as implemented in the VisitTreeWithoutRecursion() method.

• Lines 17–18: We make a stack of nodes to store the tree and push the root node on it.

• Lines 20–21: We iteratively pop out the top node from the stack and print it.

• Lines 22–27: We push its right and/or left subnodes (if they exist) onto the stack, continuing until the stack is empty. We push the right child before the left child because of the stack data structure, so we get the left child first when we pop values from the stack.

Finally, we try it out by making a binary tree and adding some nodes.

Note: You’re encouraged to play around with the above code.

Recursive preorder traversal

In general, recursion implicitly uses a stack data structure. In recursion, when we reach the base point, it starts unwinding. For that reason, in the code above, we used the stack data structure to traverse the tree without recursion.

In a tree, the leaf node is the base point. Reaching that point node becomes null, and we reach the base point. To simulate the recursion, we need to apply stack explicitly instead of implicitly. Let’s go through the code snippet below to understand what happens inside.

This is the part where we defined and declared the static TreeNodeClass class:

static class TreeNodeClass {
    String data;
    BinaryTreeWithoutRecursion.TreeNodeClass left, right;

    TreeNodeClass(String value) {
        this.data = value;
        left = right = null;
    }

    boolean isLeaf() {
        return left == null ? right == null : false;
    }
}

// root of the binary tree from where we start our journey
BinaryTreeWithoutRecursion.TreeNodeClass root;

We want three node objects, naming them left, right, and root. We also need a String data type variable to store our values. The advantage of making the class static is it will run the program faster.

The only problem with using iteration lies in its length of code. We can’t make it as concise and readable as we can do with recursion.

Let’s try to do the same preorder tree traversal recursively. Comparing the two code snippets will give us a good idea about why binary tree traversal is usually done recursively.

If you’re a Java developer, you might have guessed why we have used the printf() method:

System.out.printf("%s ", node.data);

We want to store the data to build the structure. Until we reach the base case or leaf node, the function traversingPreOrderByCallingItself() calls itself and keeps adding the value to the node tree. Therefore, the output will be the same as before.

A B C D E F 

So, what are the main differences between iteration and recursion? For the preorder tree traversal algorithm, things were a little bit complicated. We needed a stack of nodes first, Then, we pushed the tree root into the stack. After that, we keep pushing the right and left child while simultaneously, we pop all nodes for each node.

But in the last coding example, the recursive method takes a node as a parameter and first calls the root node, then applies the recursive method on its left subtree and then on the right subtree on lines 27–29.