Sunday, September 18, 2011

Post-Order Binary Tree Traversal

Time Complexity - O ( n log n )
Space Complexity - O ( n log n )

For every element to be processed, we keep looping down till we reach the leaf child node. And then elements are processed while coming up.
Thus to process element n, we recursively loop (or loop to stack the elements) upto height of that node O(h)
Since going down by height, we divide the scope into half (left or right subtree) - O(h) is log n
And each time we loop (through recursion or stack) - a new layer of stack is allocated in memory

Thus for all elements -
Time & Space Complexity = nO(h) = nlog n = n log n

Any tree traversal - Inorder, PreOrder, PostOrder, BFS, DFS - are all same O(n log n)

Given a binary tree, print out the nodes of the tree according to a
bottom-up "postorder" traversal -- both subtrees of a node are printed
out completely before the node itself is printed, and each left subtree
is printed before the right subtree.

package main.java.algo.datastructures.binarytree.traversal;

import java.util.Stack;

import main.java.algo.datastructures.binarytree.Node;

/**

 ** So the tree...
       4 
      / \ 
     2   5 
    / \ 
   1   3
  / 
0.5
 
** Produces the output "1 3 2 5 4" 
** 
** http://codepad.org/QEVUNzYU
**/

public class PostOrder {
	

	/** ************************** PostOrder : Recursive ************************** **/


	//Produces the output "1 3 2 5 4".
	public void postOrderRecursive(Node node) {
		
		if (node == null)
			return;

		// first recur on both subtrees
		postOrderRecursive(node.left);
		postOrderRecursive(node.right);

		// then deal with the node
		System.out.print(node.data);
	}
	
	
	/** ************************** PostOrder : Iterative ************************** **/

	/**
				       4 
				      / \ 
				     2   5 
				    / \ 
				   1   3
	   
	   
	 **/
	
	
	// Why do we need a VISITED flag in POST ORDER??
	
	// First remember that in post order, when we start reading from stack, we do peek first and not pop as in inorder and preorder.
	
	//	Lets consider if there was NO visited flag -
	//	
	//	1) After 1st postOrderPushLeftChildsToStack. Stack -> 4,2,1
	//	2) Peek 1 - pushleftChilds(1.right) - since there was no child of 1, stack remained same. Stack -> 4,2,1
	//	3) Pop 1, Process 1. Stack -> 4,2
	//	4) Now Stack -> 4,2. Peek 2 - pushleftChilds(2.right) - added 3. Stack -> 4,2,3
	//	5) Pop 3, Process 3. Stack again became -> 4,2
	//	
	//	Now if we did not kept visited flag - it would again then go to step 4 and go into infinite loop of steps 4 and step 5.
	//	By keeping visited flag, node 1 and node 3 is marked visited now. So, when after step 5, when it again goes to step 4, 
	//	there is no unvisted child of 2 that could be added to stack. To even after step 4, Stack -> 4,2
	//	Then 2 was popped and stack became Stack -> 4.
	//	
	//	Thus with visited flag, we avoid infinite loops as in DFS graph traversal.
	 
	
	class BTNode {
		Object data;
		BTNode left;
		BTNode right;
		
		// post order is achieved with help of DFS, using a visited flag
		boolean visited;
		
	}

	public void postOrderIterative(BTNode n) {
		//using stack
		Stack<Object> s = new Stack<Object>();
		
		// what doit(n.left) does
		postOrderPushLeftChildsToStack(s, n);

		// what happens when doit(n.right) is called
		while (!s.isEmpty()) {
			BTNode t = (BTNode) s.peek(); // Note it is peek, not pop.
			t = t.right;
			// what doit(n.left) does
			postOrderPushLeftChildsToStack(s, t);
			
			// processing on a node
			Node top = (Node) s.pop(); // Here current node to processed is the one on top of stack = s.pop()
			process(top);
		}
	}

	// it does what doit(n.left) was doing
	// pick only non visited items next time. Once visted, mark them as visited.
	public void postOrderPushLeftChildsToStack(Stack<Object> s, BTNode n) {
		while (n != null && n.visited == false) {
			n.visited = true;
			s.push(n);
			n = n.left;
		}
	}
	
	
	
	public void process(Node n) {
		System.out.println(n.data);
	}
	
	public void process(BTNode n) {
		System.out.println(n.data);
	}
}

1 comment: