Depth-First Search - Preorder Traversal of a Binary Tree

Intro

In the previous post, we've covered the Depth-First Search algorithm.
We said that there are three strategies for the DFS traversal: Preorder, Inorder, and Postored. In this post, we'll cover the Preorder traversal of a Binary Tree.

Preorder Traversal - How does it work?

In the Preorder Traversal, we first handle (or in this case print) the root node. After that, we handle its left child, then the right child. So the order is Root, Left, Right.

Let's say we have the following tree structure:

During the Preorder traversal, we handle/print the elements in the following order: Root, Left, Right.
So the output should be: 1, 2, 4, 5, 3, 4, 6, 7

Preorder Traversal implementation

We can implement the algorithm in two ways: recursive and iterative.

First, let's create a Tree class and a Node class:

class Node {
  Node left;
  Node right;
  int value;

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


class Tree {

  Node root;
}

Recursive Preorder

Below is the implementation of the recursive method preorder:

    public void preorder(Node root) {
1|     if(root == null) { // BASE CASE
2|       return;
       }

3|     System.out.println(root);
4|     preorder(root.left);
5|     preorder(root.right);
    }

As you can see, this method accepts the root node as a parameter, and its base case is when the root is null. The root will be null when we get to the end of the tree - to the leaf node.

In recursion, the most important part is the stack of the method calls. 

To understand how this recursive preorder method works, we need to keep track of the internal stack that gets created when we start calling the preorder method recursively.

Example:

We have the tree structure in the image above. 

When we first call the preorder method, we pass the root node, which is 1.

Now, we check if the root is null, and it is not. We continue.

We print the root node, then we call the recursive method passing the left child of the current root, which is 2.

So at this moment, we have the method stack like this:

When the R - is the root and L is the line where we stopped. 

We need to keep track of the lines so that when the one method call finishes and the row gets removed from the method stack, we need to know where we left off in the previous method call so that we can continue with the execution.

So in this case, where we have the root as 1, we stopped at line 4, where we call the preorder with the left child.

Now we are back at the beginning of the method, and the current root is 2. We check the base case, and since the root is not null, we print it, and then we call the preorder passing the left child of the current root - which is 4.

The current stack:

Now, we print the 4, which is the current root, and we call the preorder passing the left child of the current root, which is null since the current root (number 4) is a leaf node.

The stack:

Now, we are at the beginning of the preorder method, where the root node is null. We check the base case, we see that the root is null and we just exit the method. In this case, the current row in the method stack gets deleted, because we finished with the current method execution.

The stack:

Now, we are back at the row where the root was number 4. We also see that we left off at the line number 4. So we continue with the execution by calling the preorder method on line 5, passing the right child of the current root - which is also null - since the number 4 is a leaf node and has no children.

Now, the stack looks like this: (note: we've changed the line for the root 4, to number 5)

Since the root is null, we are finishing with the execution, and the current row gets removed from the stack. Now we are again on the row where the root was 4, and we left off at the line number 5.

We continue with the current method execution, and since there are no more commands after line 5, we exit the method call, and the current row gets removed from the stack.

Now we are at the row where the root was 2, and we left off at line number 4, where we passed the left child. Now, we proceed and pass the right child (number 5) to the preorder method on line 5.

Stack: 

Now, the current root is 5, and since it is a leaf node, the both left and right child will be passed as null, both method executions will be over when we check for the base case, so we are again at the row, where the root is 5 and line number is also 5. 

The stack:

We continue and exit the current method call since there are no more instructions after line number 5 and we are back at the row where the root is number 2. We see that we left off at line number 5, so we exit this method call too. And we are now back at the row where the root was 1 and the line we left off is 4.

The stack:

Now we continue and pass the right child (number 3) to the preorder method at line 5. 

The stack:

Now, since the root is not null, we continue and print the root ad line number 3. Next, we pass its left child (number 6) to the preorder method at line number 4. 

Stack: 

Now, we print the root and since the current root is a leaf node, we will be passing null for both the left and right child, so those method executions will be finished when we check for the base case. 

And we are now back at the row where the root is 6 and the line we left off is 5.

Stack:

Now, since there are no more lines after line 5, we exit the current method execution, and the current row gets removed from the stack and we are back at the row where the root is 3 and the line is 4.

We continue and pass the right child (number 7) of the current node (number 3) to the preorder method on line 5. 

The stack:

And now, since the current node - number 7 - is a leaf node, we will be passing null for both the left and right child, and those method executions will be finished when we check the base case and both rows will be deleted from the method stack.

And now, we are at the row where the root is 7 and the line is 5.

Stack:

Since the current line is 5 and there are no more lines, we exit the method call and we are back at the row where the root is 3. The line is also 5 since we've already passed both the left and right child. We finished this method call also, and the rows got removed from the stack. 

Now we are all the way back when the root was 1 and the line was 5.

Stack:

Now, since there are no more instructions after line 5, we are finishing with this method execution also, and the row got removed from the stack. The stack is now empty and we finished traversing the tree.

And that is how we can keep track of the method call stack and both root and line values.

We should always try to keep a notepad and a pen when we are dealing with the recursion since it is much easier to keep track of what is going on with the recursive calls and the values.

Iterative

Here, since we can not rely on the method call stack, like in recursion, we need to find other ways to keep track of the nodes that we visited so that we can go back to them when needed.

Stack data structure to the rescue! 

We can implement and use our own Stack data structure. The stack is a LIFO data structure, which means the element we last added will be the first one that popped out of the stack.

Let's see the iterative implementation of the preorder method:

public void preorder() {
  Stack<Node> stack = new Stack<>();
  stack.push(root);

  while (!stack.isEmpty()) {
    Node current = stack.pop();

    System.out.println(current.value);

    if (current.right != null) {
      stack.push(current.right);
    }

    if(current.left != null) {
      stack.push(current.left);
    }
  }

Here, at the very beginning, before we start with the looping, we add the root node to the stack.

We are iterating until we find that the stack is empty, which would mean that we have gone through all the elements.

Inside the while loop, we pop the last element we have added to the stack, which is in the first iteration - the root node.

We print it, and we add first its right child, and then its left child to the stack (if the values are not null).

Why do we add first the right child, and then the left? It's because in the next iteration as the first step, we are popping the last added element out of the queue, and the last element is the left child, and we want to handle the left child before the right child.

Now, when the left child of the root node is the current node (since we popped it from the stack), we print it and push its right and the left child to the queue, so in the next iteration, we pop its left child, and so on...

When we get to the leaf node, and we don't add any more nodes to the queue (since both the right and left child are null), we pop the right child in the next iteration, since that is the node we added last.

It is really important to keep track of what elements we have added to the queue and in which order to better understand this code. I advise drawing on the white table or using paper and pen for this.

So similar to what we did above for the recursive preorder method, just we don't need to keep track of the lines.

Preorder traversal - analysis

The time complexity of the Preorder traversal is O(n) since we need to visit every node in the tree.

Space complexity is O(1) for recursive - unless we want to count the stack that is being created in the background - then it is O(n).

For the iterative way - space complexity is O(n) since we are creating a Stack data structure that requires additional space in memory. 

The size of the stack is proportional to the number of nodes inside the tree.