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.
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.