Postorder Tree Traversal (DFS) in java

# Postorder Tree Traversal (DFS) in java

In our previous post we had discussed about different approaches of implementing Preorder and Inorder tree traversal. In this article we shall discuss steps and different ways of implementing Postorder tree traversal.

There are different ways to traversal a tree in DFS such as:

1. Preorder
2. Inorder
3. Postorder

Here in this article, we shall discuss steps and different approach of implementing Postorder tree traversal.

### Steps for Postorder Tree Traversal are :

1) Traverse the left subtree, i.e., call Postorder(left-subtree)
2) Traverse the right subtree, i.e., call Postorder(right-subtree)
3) Visit the root. Postorder Traversal of above tree is 70, 40, 50, 20, 60, 30, 10

Time Complexity: O(n)

1) Recursive
2) Iterative

### Recursive solution for Postorder Tree Traversal :

Recursive solution for Postorder Traversal is similar to the steps we had discussed above. Algorithm for recursive solution is

```1) Traversal left node i.e postorder(root.left)
2) Traversal right node i.e postorder(root.right)
3) Print root node```

Code for recursive solution

```package com.code2succeed.tree;

import java.util.Stack;

public class PostorderTraversal {
public static class Node {
private int data;
private Node left;
private Node right;

public Node(int data) {
this.data = data;
}
}

public void postorder(Node root) {
if(root != null) {
//Traversal left subtree
postorder(root.left);
//Traversal right subtree
postorder(root.right);
//print root
System.out.print(root.data+" ");
}
}

public static void main(String[] args) {
Node root = new Node(10);
Node node20 = new Node(20);
Node node30 = new Node(30);
Node node40 = new Node(40);
Node node50 = new Node(50);
Node node60 = new Node(60);
Node node70 = new Node(70);

root.left = node20;
root.right = node30;
node20.left = node40;
node20.right = node50;
node40.left = node70;
node30.right = node60;

PostorderTraversal pt = new PostorderTraversal();
System.out.println("Postorder Traversal recursive solution : ");
pt.postorder(root);
}
}
```

Output

```Postorder Traversal recursive solution :
70 40 50 20 60 30 10```

### Iterative solution for Postorder Traversal

To implement iterative solution for Postorder Traversal, we will be using Stack data structure. Algorithm for iterative solution is

```1) create stack and initialize currentNode as root.
2) While currentNode isn't null, do the following...
- if currentNode.right != null, push the right node to stack.
- then push cuurrentNode to stack.
3) Pop an node from stack and set it to currentNode.
- if currentNode has right child and it is at top of stack. Pop the right child,
push currentNode back to stack and assign currentNode = currentNode.right
- else print node data and assign currentNode = null;
4) Repeat step 2 and 3 till stack empty```

Code for iterative solution

```package com.code2succeed.tree;

import java.util.Stack;

public class PostorderTraversal {
public static class Node {
private int data;
private Node left;
private Node right;

public Node(int data) {
this.data = data;
}
}

public void postorderIterative(Node root) {
if(root == null) return;
Stack<Node> stack = new Stack<Node>();
Node currentNode = root;

while(true) {
if(currentNode != null) {
if(currentNode.right != null) stack.push(currentNode.right);
stack.push(currentNode);
currentNode = currentNode.left;
continue;
}

if(stack.empty()) {return;}
currentNode = stack.pop();

if(currentNode != null && !stack.empty() && currentNode.right == stack.peek()) {
stack.pop();
stack.push(currentNode);
currentNode = currentNode.right;
}else {
System.out.print(currentNode.data+ " ");
currentNode = null;
}
}
}

public static void main(String[] args) {
Node root = new Node(10);
Node node20 = new Node(20);
Node node30 = new Node(30);
Node node40 = new Node(40);
Node node50 = new Node(50);
Node node60 = new Node(60);
Node node70 = new Node(70);

root.left = node20;
root.right = node30;
node20.left = node40;
node20.right = node50;
node40.left = node70;
node30.right = node60;

PostorderTraversal pt = new PostorderTraversal();
System.out.println("\nPostorder Traversal iterative solution : ");
pt.postorderIterative(root);
}

}
```

Output

```Postorder Traversal iterative solution :
70 40 50 20 60 30 10```