Postorder Traversal of Binary tree

Introduction

Our today’s topic is the Postorder Traversal of a Binary tree. If you are reading this article, you must be familiar with binary trees, which is the prerequisite for this topic. Let’s understand the difference in traversal between linear data structures and non-linear data structures. Unlike linear data structures (Array, Linked List, Queues, Stacks, etc.), which can only be traversed in one logical manner, trees can be traversed in various ways, which are:

Depth-First Traversal: In depth-first search (DFS Algorithm), the search tree is deepened as much as possible before going to the next sibling.

• Pre-order traversal ( Root Left-Right )
   
• In-order traversal ( Left Root Right )
   
• Postorder traversal ( Left Right Root )
   

Breadth-First Traversal: In Breadth-first search(BFS), the nodes are traversed in a level-wise order.

Although there is a possibility to perform a post-order traversal of the binary tree recursively, in this article we’ll be exploring post-order traversal using the Iterative approach, which will use stacks to perform the traversal of the tree.

Check out, Iterative Preorder Traversal of Binary Tree | Part 2 

Before any further due, let’s get started:

What is a Postorder Traversal in a Binary Tree?

A binary tree postorder traversal is a method of listing all of the tree's leaves and nodes so that for each node, all of its left children come before all of its right children, which come before the node itself. In simple words, Postorder traversal is a binary tree traversal approach in which you visit the left subtree first, then the right subtree, and finally the root.

LeftSubtree -> RightSubtree -> Root

Consider the following example of a binary tree traversal utilizing the post order.

In the preceding example, because the leftmost node is A, it is visited first. Following that, since D is the root node of C and E, the nodes C and E will be visited before the D node. The B node is now the last one to be visited in the left subtree. Now, the left subtree is visited, and because the algorithm expects the root to be visited last, it moves to the right subtree and processes each node in the same manner as it did for the left subtree.

Now that you are familiar with postorder traversal let’s look at the approaches we can perform to traverse a binary tree. As we are attempting to traverse the tree iteratively, thus we’ll be needing an auxiliary stack to process each node.

Must Read Recursive Binary Search.

Algorithm of Postorder Traversal

Below is the algorithm for the postorder traversal of all the nodes of the binary tree:

Step 1: Check if the current node is NULL; if yes, return.

Step 2: Traverse the left subtree recursively.

Step 3: Traverse the right subtree recursively.

Step 4: Visit the current node.

Step 5: END

This algorithm can be implemented using either recursion or an iterative approach. The recursive approach is typically easier to understand, while the iterative approach can be more efficient in some cases.

When using Recursion to perform a postorder traversal, the algorithm maintains a call stack that stores the nodes that still need to be visited. The stack is initially populated with the root node of the tree, and the algorithm continues until the stack is empty.

How PostOrder traversal of the Binary tree works?

Postorder traversal of a binary tree is a recursive algorithm that visits the nodes in the following order:

1. Traverse the left subtree.
    
2. Traverse the right subtree.
    
3. Visit the root node.
    

Here are the steps involved in performing a postorder traversal of a binary tree:

• Recursively traverse the left subtree using postorder traversal.
   
• Recursively traverse the right subtree using postorder traversal.
   
• Visit the current node and perform any desired operations.
   

Now, let's look at an example of Postorder traversal considering the following tree:

In the below image, we have a binary tree with all non-visited nodes. Now, let us traverse the tree using Postorder Traversal.

Step 1: In the above example, 33 is the root node from where we are going to start our traversal. Firstly, we will traverse to the left subtree of node 33, i.e., 27. Again, node 27 will traverse in Postorder to its left subtree 13. Now, node 13 has no left or right subtree, so let's print 13 and mark it as visited and move up towards 27.

Step 2: Node 27 has no right subtree; therefore, we will mark 27 visited, print it and move up toward the right subtree of root node 33.

Step 3: Now, node 45 will also follow the Postorder sequence and will go toward left subtree 42. Again, 42 will go towards its left subtree 35. As 35 has no subtrees, we will print it and mark it visited and then move up towards node 42.

Step 4: Now, node 42 has no right subtree. Thus we will mark it visited, print it and then move up towards node 45.

Step 5: Node 45 will go towards its right subtree 53. Now, 53 has no left or right subtree. So, we mark it visited and move back towards node 45 again.

Step 6: Now both subtrees of 45 are visited, so we will mark 45 visited and go up toward the root node 33.

Step 7: Now, at last, both subtrees of node 33 are visited. So, mark 33 visited and print it, and our Postorder traversal is finished.

The final output of Postorder traversal: [13, 27, 35, 42, 53, 45, 33]

Approaches to Implement Postorder Traversal of Binary Tree

1. Using two stacks: In this section, we’ll learn how two stacks can assist in traversing the binary tree.
    
2. Using one stack: This is the more efficient approach to solving this problem. We have discussed this approach in another blog.

Method 1: Using two stacks

We can use two stacks to implement the Postorder traversal. The goal is to acquire the reversed postorder elements in the stack and then pop the elements one by one from the stack, as the stack adheres to the LIFO principle. The question of how to obtain the reversed order of the postorder items emerges. This problem's answer can be reached by combining two stacks. The second stack is utilized to obtain the postorder items in reverse order.

The steps for implementing postorder utilizing two stacks are as follows:

1 - We'll start by pushing the root to the top of the stack.

2 - Second, we'll run a while loop that will keep running until the first stack becomes empty and process the below steps.

• A node from the first stack is popped and pushed into the second.
   
• Push the left and right child of the popped node to the first stack.

3 - The data from the second stack will be printed.

Consider the above example, and let’s try to understand each step in detail before moving to the Implementation:

1. Push 1 to the first stack.

      First stack: 1

      Second stack: Empty
 

2. Pop 1 from the first stack and push it to the second stack. 

    Push left and right children of 1 to the first stack.

      First stack: 2, 3

      Second stack: 1
 

3. Pop 3 from the first stack and push it to the second stack.  

   Push the left child of 3 to the first stack.

      First stack: 2, 6 

      Second stack: 1, 3
 

4. Pop 6 from the first stack and push it to the second stack.

      First stack: 2

      Second stack: 1, 3, 6
 

6. Pop 2 from the first stack and push it to the second stack.  

    Push left and right children of 2 to the first stack.

      First stack: 4, 5

      Second stack: 1, 3, 6, 2
 

7. Pop 5 from the first stack and push it to the second stack. 

      First stack: 4

      Second stack: 1, 3, 6, 2, 5
 

8. Pop 4 from the first stack and push it to the second stack.

      First stack: Empty

      Second stack: 1, 3, 6, 2, 5, 4
 

The algorithm stops here since there are no more items in the first stack. 

Observe that the contents of the second stack are in postorder fashion. Print them. 

Algorithm

Step 1: Create two empty stacks -> stack1 and stack2.  

Step 2: Push the root node on stack1.  

Step 3: TreeNode* current = NULL  

Step 4: while(!stack1.empty())  

             current = top of stack1  

             pop current from stack1  

             push current on stack2  

             if (current->left!= Null)  

                 push current->left on stack1  

             if(current->right!=NULL)  

                 push current->right on stack1   

Step 5: while(!stack2.empty())  

             current = top of stack2  

             print current->value  

             pop current from the stack2

Implementation in C++

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    stack<TreeNode*> s1, s2;
    s1.push(root);

    while (!s1.empty()) {
        TreeNode* node = s1.top();
        s1.pop();
        s2.push(node);

        if (node->left) {
            s1.push(node->left);
        }

        if (node->right) {
            s1.push(node->right);
        }
    }

    while (!s2.empty()) {
        cout << s2.top()->val << " ";
        s2.pop();
    }
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    cout << "Postorder traversal: ";
    postorderTraversal(root);

    return 0;
}

Output

Postorder traversal: 4 5 2 6 3 1

Time Complexity:- The time complexity is O(n) (where n is the number of nodes in the tree) because of the work we do in the while loops.

Space Complexity:- The space complexity is O(n) (where n is the number of nodes in the tree) because of the space taken by the two stacks.

To know more about conceptual knowledge and the implementation of the code, watch this video tutorial.

Implementation in Java

import java.util.Stack;

class Node {
    int data;
    Node left, right;

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

public class IterativePostorder {
    static Node root;

    static void postOrderIterative(Node node) {
        if (node == null)
            return;

        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();

        stack1.push(node);

        while (!stack1.isEmpty()) {
            Node current = stack1.pop();
            stack2.push(current);

            if (current.left != null)
                stack1.push(current.left);
            if (current.right != null)
                stack1.push(current.right);
        }

        while (!stack2.isEmpty()) {
            Node current = stack2.pop();
            System.out.print(current.data + " ");
        }
    }

    public static void main(String[] args) {
        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);
        root.right.left = new Node(6);

        System.out.println("Postorder traversal (Iterative):");
        postOrderIterative(root);
    }
}

Output

4 5 2 6 3 1 

Time Complexity:- The time complexity is O(n) (where n is the number of nodes in the tree) because of the work we do in the while loops.

Space Complexity:- The space complexity is O(n) (where n is the number of nodes in the tree) because of the space taken by the two stacks.

Method 2: Using one stack

An efficient way to visit every node of a binary tree in postorder traversal order, without using recursion, is through the iterative postorder traversal method using a single stack. This algorithm simulates the recursive call stack by keeping track of nodes to visit and their order using only one stack. The process begins by initializing an empty stack and a pointer to the root of the tree. The algorithm then uses a loop to iterate through each node until all nodes have been visited or the stack is empty. In each iteration, the algorithm either pushes the current node onto the stack and moves the current node pointer to its left child or pops the top node from the stack and visits it if its right child is null or has already been visited. By eliminating the function call stack used in the recursive approach, this method improves efficiency.

Algorithm

1. Create an empty stack and initialize a pointer to the root of the tree.
    
2. Initialize a pointer to the last visited node to null.
    
3. Loop while the current node pointer is not null or the stack is not empty:
   
   
   1. If the current node is not null, push it onto the stack and set the current node pointer to its left child.
       
   2. If the current node is null, retrieve the top node from the stack.
      
      
      1. If the right child of the top node is not null and not equal to the last visited node, set the current node pointer to the right child.
          
      2. If the right child of the top node is null or equal to the last visited node, visit the top node, set the last visited node pointer to the top node, and pop it from the stack.
          
4. After the loop completes, the nodes of the binary tree will have been visited in postorder traversal order.

Note that this algorithm uses a single stack to simulate the recursive call stack used in the recursive implementation of postorder traversal. The key idea is to use the stack to keep track of the nodes to visit and the order in which to visit them.

Implementation in C++

#include <iostream>
#include <stack>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

void postorder(Node* root) {
    stack<Node*> s;
    Node* current = root;
    Node* lastVisited = nullptr;

    while (current != nullptr || !s.empty()) {
        if (current != nullptr) {
            s.push(current);
            current = current->left;
        } else {
            Node* topNode = s.top();

            if (topNode->right != nullptr && topNode->right != lastVisited) {
                current = topNode->right;
            } else {
                cout << topNode->data << " ";
                lastVisited = topNode;
                s.pop();
            }
        }
    }
}

int main() {
    Node* root = new Node{1, nullptr, nullptr};
    root->left = new Node{2, nullptr, nullptr};
    root->right = new Node{3, nullptr, nullptr};
    root->left->left = new Node{4, nullptr, nullptr};
    root->left->right = new Node{5, nullptr, nullptr};

    cout << "Postorder traversal: ";
    postorder(root);

    return 0;
}

Output

Postorder traversal: 4 5 2 3 1

Implementation in Java

import java.util.Stack;

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

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

class Main {
    static void postorder(Node root) {
        Stack<Node> s = new Stack<>();
        Node current = root;
        Node lastVisited = null;

        while (current != null || !s.empty()) {
            if (current != null) {
                s.push(current);
                current = current.left;
            }
            else {
                Node topNode = s.peek();

                if (topNode.right != null && topNode.right != lastVisited) {
                    current = topNode.right;
                }
                else {
                    System.out.print(topNode.data + " ");
                    lastVisited = topNode;
                    s.pop();
                }
            }
        }
    }

    public static void main(String[] args) {
        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);

        System.out.print("Postorder traversal: ");
        postorder(root);
    }
}

Output

Postorder traversal: 4 5 2 3 1

Time Complexity:- The time complexity is O(n) (where n is the number of nodes in the tree) because of the work we do in the while loops.

Space Complexity:- The space complexity is O(n) (where n is the number of nodes in the tree) because of the space taken by the one stack.

Now, you have understood the approach; it’s time to implement the code on your own in your favorite programming language on Coding Ninjas Studio. Complete your turn before it’s too late.

Check out this problem - Mirror A Binary Tree

Advantages and disadvantages of Postorder traversal

Listed below are examples outlining the advantages and disadvantages of postorder traversal.

Advantages

• It can be used to delete a binary tree from memory because it visits the child nodes before the parent nodes.
   
• It can be used to evaluate arithmetic expressions in postfix notation because the operators are encountered after their operands.
   
• It can be used to find the height of a binary tree because the height of a node is equal to the maximum height of its child nodes plus one.
   
• It can be used to implement certain types of binary tree balancing algorithms because it allows for easy computation of balance factors and subtree heights.

Disadvantages

• It is more complex than preorder and inorder traversals and can be more difficult to implement and understand.
   
• Postorder traversal requires additional memory to maintain the call stack, which can be a problem for very large trees.
   
• It may not be the most efficient traversal method for certain use cases, as it can result in a larger number of cache misses and branch mispredictions than other methods.
   
• In some cases, postorder traversal may not be necessary or desirable for a particular application or problem.

Frequently Asked Questions

What is Postorder traversal sequence?

The Postorder traversal sequence is left-right-root, i.e., start from the left subtree followed by the right subtree and then the root node.

Where does Postorder traversal start?

Postorder traversal starts at the root node and visits the left subtree, the right subtree, and finally, the root.

What is the function of Postorder?

The function of Postorder is to visit nodes in a binary tree and process child nodes before their parent.

What is the difference between inorder and Postorder traversal?

In Postorder, nodes are visited in the order left-right-root, while in Inorder, it's left-root-right.

What is inorder preorder and postorder traversal of a binary tree?

In binary tree traversals, Inorder explores the left subtree, root, and right subtree. Preorder begins with the root, then the left subtree, and ends with the right subtree. Postorder investigates the left subtree and right subtree and finishes with the root.

How do you find the Postorder traversal of the binary tree?

To find the Postorder traversal of a binary tree, start from the root node, then recursively traverse the left subtree followed by the right subtree, and finally visit the root of the tree.

Why is it called post-order traversal?

Postorder traversal is called postorder because it visits the root node of the tree at last after visiting the left and right subtree.

When to use postorder traversal?

If you know you need to inspect all the leaves before any nodes, you choose post-order, so you don't waste time inspecting roots in search of leaves.

Conclusion

To summarize, we’ve covered the tree traversal iteratively using the postorder DFS based on LRR( Left right root) algorithm. The postfix expression of an expression tree can be obtained using postorder traversal. Moreover, postorder traversal is also used when there is a need to visit the child nodes before the Root node. Postorder traversal is complicated among all the other traversals but is efficiently utilized in computer science. Along with that, a tree can be deleted from leaf to Node by using the postorder traversal. 

So, in this article, we looked at postorder traversal with two stacks; however, there is a more interesting and memory-friendly way to traverse the tree with a single stack.

Recommended Reading:

• BFS v/s DFS for Binary Trees
• Practise Problems

Recommended problems -

• Zig Zag Tree Traversal 
• Preorder Traversal
   

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Leaning Ninja!