Depth-First Search - Postorder Traversal of a Binary Tree

Intro

The Postorder traversal is another strategy of the Depth-First Search algorithm.
In the previous posts, we covered the Preorder and Inorder traversals of a Binary Tree.

Here, we will go through and understand the Postorder traversal and see how we can implement it.

Postorder Traversal - How does it work?

In the Postored traversal, we traverse the tree by first handling the left child, then the right child, and at the end, we handle the root node. So the order is Left, Right, Root.

Let's say we have the following tree structure:

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

Postorder 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 Postorder

Below is the implementation of the recursive method postorder:

public void postorder(Node root) {
  if(root == null) { // BASE CASE
    return;
  }

  postorder(root.left);
  postorder(root.right);
  System.out.println(root.value);
}

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 try to work with the child of a leaf node (The leaf node does not have children). 

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

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

Have a look at the Preorder traversal post, where we have gone through every step of the recursion method calls and we kept track of everything that is going on, including the current root element and the program lines.

Use the same approach to keep track of the recursion process here, to better grasp what is going on under the hood as we execute the method postorder recursively.

Iterative Postorder

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.

Unlike the Preorder and Inorder traversals where we use one stack, for the Postorder, we will use two stacks - one for storing the nodes as we visit them, and the other stack for printing the nodes in postorder.

Code:

public void postorder(Node root) {
  if (root == null) {
    return;
  }

  Stack<Node> stack = new Stack<>();
  Stack<Node> out = new Stack<>();
  stack.push(root);

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

    out.push(node);

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

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

  while (!out.isEmpty()) {
    Node node = out.pop();
    System.out.print(node.value + " ");
  }
}

As you can see, the above code is simply a loop version of the corresponding recursive solution.

In the first while loop, we iterate as long as the stack is not empty, and we first pop the last added node, then we add it to the out stack, and we add its left and right nodes to the same stack. And that is it.

When the first while loop finishes, we have out queue where the elements are stored in exactly the order we want. Now inside the second loop, we start popping the elements and printing them.

The result after printing is 4, 5, 2, 6, 7, 3, 1.

Postorder traversal - analysis

The time complexity of the Postorder 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 (two stacks in this case) that requires additional space in memory. 

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