Post-order Traversal of a Binary Tree

Algorithm/Insights

In the post-order traversal for a given node 'n',
1. We first traverse left-subtree of 'n' by calling printPostorder(n.left)
2. Then we traverse right-subtree of 'n' by calling printPostorder(n.right)
3. And finally we visit node 'n' itself.

Please checkout the code section(printPostorder()) with visualization for illustration.

Code Snippet

			
package com.ideserve.nilesh.questions;

public class Tree {

	private TreeNode root;
	
	public TreeNode getRoot() {
		return root;
	}

	class TreeNode {
		
		private int data;
		private TreeNode left;
		private TreeNode right;
		
		public TreeNode(int data, TreeNode left, TreeNode right) {
			super();
			this.data = data;
			this.left = left;
			this.right = right;
		}

		public int getData() {
			return data;
		}

		public void setData(int data) {
			this.data = data;
		}

		public TreeNode getLeft() {
			return left;
		}

		public void setLeft(TreeNode left) {
			this.left = left;
		}

		public TreeNode getRight() {
			return right;
		}

		public void setRight(TreeNode right) {
			this.right = right;
		}

		public TreeNode() {
			super();
		}

		public TreeNode(int data) {
			super();
			this.data = data;
		}
		
		@Override
		public String toString() {
			return data+""; 
		}
	}

	public static void main(String[] args) {
		Tree tree = new Tree();
		tree.createSampleTree();
		tree.printPostorder();
	}

	/*
	 * Create a sample tree
	 * 				1
	 * 		2				3
	 * 4		5		6		7
	 * 
	 */
	public void createSampleTree() {
		root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));		
	}

	/*
	 * Print postorder traversal
	 */
	public void printPostorder() {
		printPostorder(root);
	}
	
	private void printPostorder(TreeNode root) {
		if(root == null) {
			return;
		}
		printPostorder(root.getLeft());
		printPostorder(root.getRight());
		System.out.print(root.getData() + " ");
	}
}
		

Order of the Algorithm

Time Complexity is O((n))
Space Complexity is O((1))