Postorder Traversal of Binary Tree - Recursive

In the previous tutorial, we have seen inorder traversal of a binary tree with the help of recursion. Now, in this tutorial we will see Postorder traversal of a binary tree. In this, firstly, left of the tree is visited right of tree is visited same and at last root is visited and printed same applies for subtree. Postorder traversal is also DFS(depth-first-search)algorithm to traverse the whole tree.
Postorder Traversal: Left Right Root.
Let us take an example.

The Postorder Traversal of above given Binary Tree will be: 6, 7, 5, 20, 30, 10, 2

Explanation:

1. If we encounter any node which is null we will return back (this will be the base condition)
2. Recur to the left subtree using node.left
3. Then recur to the right subtree using node.right
4. Print the node value
The same process gets repeated until whole tree is traversed.

Algorithm:

1. if (node == null) return
2. visit the left subtree.
3. visit the right subtree.
4. print the node.

Recursive code of Postorder Traversal is implemented below:

• Java

public class Postorder {

    public static class Node {

        int val;

        Node left, right;

        // Constructor

        Node(int val) {

            this.val = val;

            left = right = null;

        }

    }

    public static void main(String[] args) {

        /*

         * Creating Binary Tree The created binary tree is same as in the above given

         * figure (refer figure for reference)

         */

        Node root = new Node(2);

        root.left = new Node(5);

        root.right = new Node(10);

        root.left.left = new Node(6);

        root.left.right = new Node(7);

        root.right.left = new Node(20);

        root.right.right = new Node(30);

        // calling postorder method

        System.out.print("Postorder Traversal is: ");

        postorder(root);

    }

    public static void postorder(Node node) {

        if (node == null)

            return;

        // recur to the left subtree

        postorder(node.left);

        // recur to the right subtree

        postorder(node.right);

        // Printing the node

        System.out.print(node.val + " ");

    }

}

Output:

Postorder Traversal is: 6 7 5 20 30 10 2

Complexity Analysis:

Time Complexity: O(n), where n is number of nodes in tree. This is because, we are traversing the each node of tree at once.

Space Complexity: We have not used any extra space for storing the nodes values, so O(1) can be considered as space complexity.

---

Also See:

1. Preorder Traversal using Recursion.
2. Inorder Traversal using Recursion.