Postorder Tree Traversal

Given a binary tree, return the post-order traversal of its nodes’ values.

For traversing a binary tree in post-order fashion, we must do these three things for every node N starting from root node of the tree:
(L) Recursively traverse its left subtree. When this step is finished we are back at N again.
(R) Recursively traverse its right subtree. When this step is finished we are back at N again.
(N) Process N itself

In normal post-order traversal we visit left subtree before the right subtree. If we visit right subtree before visiting the left subtree, it is referred as reverse post-order traversal.

Example:

Input: 1 / \ 2 3 / \ 4 5 Output: Postorder (Left, Right, Root) : 4 5 2 3 1

As we can see before processing any node, the left subtree is processed first, followed by the right subtree and the node is processed at last. These operations can be defined recursively for each node. The recursive implementation is referred to as depth-first search(DFS), as the search tree is deepened as much as possible on each child before going to the next sibling.

Solution

We can use recurrsion to traverse PostOrder.

1. Traverse Left Node. 2. Traverse Right Node. 3. Process Current Node.

Code


/*
  public class TreeNode {
 
	public int val;
	public TreeNode left;
	public TreeNode right;
 
	public TreeNode(int x) {
		val = x;
	}
 
}
*/
public class PostOrderTraversal {

	public static void main(String[] args) {
		TreeNode root1 = new TreeNode(1);
		TreeNode root2 = new TreeNode(2);
		TreeNode root3 = new TreeNode(3);
		TreeNode root4 = new TreeNode(4);
		TreeNode root5 = new TreeNode(5);

		root1.left = root2;
		root1.right = root3;
		root2.left = root4;
		root2.right = root5;
		
		postOrderTrav(root1);

	}

	public static void postOrderTrav(TreeNode a) {
		if (a == null)
			return;

		postOrderTrav(a.left);
		postOrderTrav(a.right);
                System.out.print(a.val+" ");
	}
}