Binary Tree PostOrder Traversal in Java

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

1. Introduction

In this article, we will explore the concept of PostOrder traversal in binary trees, focusing on its implementation in Java. In computer science, a binary tree is a foundational data structure, and traversing it is a fundamental technique. Among the various traversal methods, PostOrder traversal is widely used due to its applications across a range of algorithms and operations.

2. What is PostOrder Traversal?

In PostOrder traversal, each node is processed after subtrees traversal. In simpler words, visit left subtree,  right subtree and then node.

3. Process of PostOrder Traversal

  • Traverse the left subtree in PostOrder.
  • Traverse the right subtree in PostOrder.
  • Visit the node.

4. Implementation

There can be two ways of implementing it:

  • Recursive
  • Iterative

4.1 Recursive Solution

Recursive solution is very straight forward. Below diagram will make you understand recursion better.

Post Order Traversal recursive solution

Code for recursion will be:

The time complexity for recursive approach is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once.

The space complexity is O(h), where h is the height of the tree. This complexity arises from the use of the call stack to handle recursion. In the worst case (a skewed tree), the height of the tree can become n, making the space complexity O(n).

4.2 Iterative Solution

Steps for iterative solution:

  • Create an empty stack s and set currentNode =root.
  • while currentNode is not NULL Do following
    • Push currentNode 's right child and then currentNode to stack s
    • Set currentNode=currentNode.left
  • Pop a node from stack s and set it to currentNode
    • If the popped node has a right child and the right child is at top of stack, then remove the right child from stack, push the currentNode back and set currentNode as currentNode 's right child.
    • Else print currentNode's data and set currentNode as NULL.
  • Repeat steps 2 and 3 while stack is not empty.
The time complexity for iterative approach is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once.

The space complexity is O(h), where h is the height of the tree. This complexity arises from the use of an explicit stack to keep track of nodes. In the worst case (a skewed tree), the height of the tree can become n, making the space complexity O(n).

5. Complete Java Program

Let’s say our binary tree is:

Binary tree

Here is complete java program for PostOrder traversal:

Run above program and you will get following output:

Using Recursive solution:
10 30 20 50 70 60 40
————————-
Using Iterative solution:
10 30 20 50 70 60 40

6. Conclusion

In this article, we covered about Binary tree PostOrder traversal and its implementation. We have done traversal using two approaches: Iterative and Recursive. We also discussed about time and space complexity for the PostOrder traversal.
Java Binary tree tutorial

Please go through java interview programs for more such programs.

Was this post helpful?

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *