Postorder traversal of a binary tree

Postorder tree traversal is a traversal method for binary tree where we traverse left subtree first and then right subtree and root node after that. This algorithm can be implemented recursively as well as using iterative method. Following diagram shows postorder traversal:

Recursive algorithm:

1. Check if the current node is empty or null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

Time Complexity:

Since, we visit every node only once, time complexity is proportional to number of nodes in binary tree.

So, Time Complexity of postorder traversal is - O(n)

public class TreeTraversal {

    static class Node {
        int data;
        Node left;
        Node right;

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

    public void postorder(Node root){
        if(root == null){
            return;
        }
        //Traverse left subtree        
        postorder(root.left);
        //Traverse right subtree        
        postorder(root.right);
        //Traverse root        
        System.out.print(root.data + " ");
    }

    public static void main(String[] args) {
        //Build Tree        
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        new TreeTraversal().postorder(node1);
    }
}