Postorder Traversal of a Binary Tree

Given a Binary Tree, the task is to Print the Postorder traversal of the given tree.
Postorder traversal is a type of depth-first traversal in binary trees. In this traversal method, you visit the left subtree, the right subtree, and then the root node. It’s called postorder because the root node is processed after the subtrees have been processed.

Input-Output Examples

Example 1:

Input:

plaintext

Output: 4, 5, 2, 3, 1

Example 2:

Input:

plaintext

Output: 40, 50, 20, 30, 10

Postorder Traversal Rules

In postorder traversal, the following steps are followed recursively:

Traverse the left subtree by recursively performing a postorder traversal on it.
Traverse the right subtree by recursively performing a postorder traversal on it.
Visit the root node (process the current node).

The traversal order is left → right → root.

Example of Postorder Traversal

plaintext

The postorder traversal for this tree is:

First, traverse the left subtree of 1 (root), which is 2.
Then, traverse the left subtree of 2, which is 4 (leaf node).
Now, traverse the right subtree of 2, which is 5 (leaf node).
Now visit 2 (root of the left subtree).
Next, traverse the right subtree of 1, which is 3.
Finally, visit the root node 1.

The postorder traversal of this tree is: 4, 5, 2, 3, 1.

Here are the implementations of postorder traversal in C++, Java, and Python.

C++ Program to implement Postorder traversal of a Binary Tree

cpp

#include <iostream>
using namespace std;

// Definition of a tree node
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = right = nullptr;
    }
};

// Function for postorder traversal (left, right, root)
void postorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }

    // Traverse the left subtree
    postorderTraversal(root->left);

    // Traverse the right subtree
    postorderTraversal(root->right);

    // Visit the root node
    cout << root->data << " ";
}

// Main function
int main() {
    // Construct the binary tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    // Perform postorder traversal
    cout << "Postorder Traversal: ";
    postorderTraversal(root);

    return 0;
}

Java Program to implement Postorder traversal of a Binary Tree

java

// Definition of a tree node
class Node {
    int data;
    Node left, right;

    Node(int value) {
        data = value;
        left = right = null;
    }
}

public class Main {
    // Function for postorder traversal (left, right, root)
    public static void postorderTraversal(Node root) {
        if (root == null) {
            return;
        }

        // Traverse the left subtree
        postorderTraversal(root.left);

        // Traverse the right subtree
        postorderTraversal(root.right);

        // Visit the root node
        System.out.print(root.data + " ");
    }

    public static void main(String[] args) {
        // Construct the binary tree
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        // Perform postorder traversal
        System.out.print("Postorder Traversal: ");
        postorderTraversal(root);
    }
}

Python Program to implement Postorder traversal of a Binary Tree

python

# Definition of a tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function for postorder traversal (left, right, root)
def postorder_traversal(root):
    if root is None:
        return

    # Traverse the left subtree
    postorder_traversal(root.left)

    # Traverse the right subtree
    postorder_traversal(root.right)

    # Visit the root node
    print(root.data, end=" ")

# Main function
if __name__ == "__main__":
    # Construct the binary tree
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)

    # Perform postorder traversal
    print("Postorder Traversal: ", end="")
    postorder_traversal(root)

Properties of Postorder Traversal

Time Complexity: O(n), where n is the number of nodes in the tree, because each node is visited exactly once.
Space Complexity: O(h), where h is the height of the tree. The space complexity is due to the recursion stack in the recursive approach, or the use of an auxiliary stack in the iterative approach.

When to Use Postorder Traversal ?

Postorder traversal is particularly useful in scenarios where you need to process the child nodes before the parent nodes. Some common use cases include:

Expression trees: Postorder traversal is used to evaluate postfix expressions.
Tree deletion: To safely delete a binary tree, postorder traversal ensures that child nodes are deleted before their parent nodes.
File systems: When performing operations that require processing all subdirectories and files before processing the parent directory.

Related Articles