Postorder Traversal
Tree traversal is a type of graph traversal and refers to visiting every node in the tree. There are various methods for traversing the tree. One of the popular traversal methods is postorder traversal which follows the rule of visiting the left subtree (first), right subtree, then the root vertex of the tree.
Binary Tree
A binary tree is a non-linear data structure in which every node has at a most maximum of two children. So, in terms of binary tree construction, we should have a node with three-pointers one to hold data and two for left and right nodes.
class Tree {
public class Node {
int data;
Node right;
Node left;
Node(int data) {
this.data = data;
left = right = null;
}
}
In this above tree class with inner node class has one instance member data and two objects of Node class left and right. For every new node, we use Node(int data ) constructor to assign data to that node and set left and right as null.
Tree.Node t = new Tree().new Node(1);
t.left = new Tree().new Node(2);
t.left.left = new Tree().new Node(4);
t.left.right = new Tree().new Node(5);
t.right = new Tree().new Node(3);
Algorithm :
- Traverse the left subtree
- Traverse the right subtree
- Visit the root
Postorder traversal for the tree is: 4 5 2 3 1
Program for iterative postorder traversal:
public void postOrder(Node root) {
Stack<Node> s = new Stack<>();
Stack<Integer> q = new Stack<>();
s.push(root);
while (!s.isEmpty()) {
Node e = s.pop();
if (e.left != null) {
s.push(e.left);
}
if (e.right != null) {
s.push(e.right);
}
q.push(e.data);
}
while (!q.isEmpty()) {
System.out.print(q.pop() + " ");
}
}
In this above program, two stacks are being used one to traverse and one for holding the data
of the node. At first, the root is pushed into the stack and while loop runs till the stack is
empty and in every iteration node's data is being pushed to the other stack and the left and right subtree
is being pushed to the traversal stack.
I hope you guys liked this article, here are some other articles you may like:
){kind=link}
0 Comments