Java Program to Perform the Postorder Tree Traversal
The Binary Tree can consist of nodes where each node contains the value and the references to its left and right children. The structure is organized hierarchically with a single root node at the top and each node having at Most Two Children.
In this article, we will learn to perform Postorder Tree Traversal.
Binary Tree Implementation
In Java, a Binary Tree can be implemented using the TreeNode class to represent each node with reference to its left and right children. Postorder traversal can be implemented recursively by visiting the left subtree then the right subtree and finally the root.
Postorder Traversal in Tree
Postorder traversal visits each node exactly once, making it O(n) in the time complexity where n is the number of nodes in a tree. The space complexity for the recursive implementation is O(h) for the Unbalanced Trees.
Postorder Traversal Algorithm
- Traverse the left subtree recursively.
- Traverse the right subtree recursively.
- Visits the root node.
Program to Perform the Postorder Tree Traversal
Below is the program to perform postorder tree traversal in Java:
// Java Program to Perform Postorder
// Traversal
// Tree Node Class
class TreeNode {
int val;
TreeNode left, right;
// Constructor
TreeNode(int item) {
val = item;
left = right = null;
}
}
class BinaryTree {
TreeNode root;
void postorderTraversal(TreeNode node) {
if (node == null)
return;
// Traverse left subtree
postorderTraversal(node.left);
// Traverse right subtree
postorderTraversal(node.right);
// Visit the node
System.out.print(node.val + " ");
}
}
// Main Class
public class Main {
// main function
public static void main(String[] args) {
// New tree Node Created
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(45);
tree.root.left = new TreeNode(12);
tree.root.right = new TreeNode(32);
tree.root.left.left = new TreeNode(56);
tree.root.left.right = new TreeNode(76);
tree.root.right.left = new TreeNode(12);
tree.root.right.right = new TreeNode(22);
System.out.println("Postorder traversal of binary tree is: ");
tree.postorderTraversal(tree.root);
}
}
Output
Postorder traversal of binary tree is: 56 76 12 12 22 32 45
Complexity of the above Method:
- Traversal: The time complexity of the post order traversal is O(n) where the n is number of nodes in the tree. The space complexity is O(n) due to function call stack.
- Insertion/Deletion: The time complexity for the insertion and deletion in the binary tree can be depending on the specific implementation.
Applications
- It can applies in Syntax Tree generation during the parsing of the Arithmetic Expressions.
- It can applies in Expression evolution where it is used to Convert Infix Expressions to the Postfix Notation.