Sunday, September 18, 2011

InOrder 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.

For an element to be at depth d, we have to do do d amount of work to reach that element. Then process it.

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)


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

import java.util.Stack;

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

/**
 ** Given a binary search tree (aka an "ordered binary tree"), 
 ** iterate over the nodes to print them out in increasing order. 
 ** 
 ** So the tree...
       4 
      / \ 
     2   5 
    / \ 
   1   3
  / 
0.5
 
** Produces the output "0.5 1 2 3 4 5". 
** 
** This is known as an "inorder" traversal of the tree.
** 
** http://codepad.org/QEVUNzYU
**/

public class InOrder {
		

	/** ************************** InOrder : Recursive ************************** **/

	
	//For each node, the strategy is: recur left, print the node data, recur right.
	public void inOrderRecursive(Node node) {
		
		if (node == null)
			return;
		 
		// left, node itself, right 

		if (node.left != null)
			inOrderRecursive(node.left);
		
		System.out.println(node.data);
		
		if (node.right != null)
			inOrderRecursive(node.right);

	}
	
	/** ************************** InOrder : Iterative ************************** **/

	
	public void inOrderIterative (Node n) {
		
		//using stack
		Stack<Object> s = new Stack<Object>();
		
		// what inOrderRecursive(n.left) does
		inOrderPushLeftChildsToStack(s, n);

		// what happens when inOrderRecursive(n.right) is called
		while (!s.isEmpty()) {
			
			Node t = (Node) s.pop();
			
			// processing on a node
			process(t);
			
			// inOrderRecursive(n.right) is called
			t = t.right;
			// what inOrderRecursive(n.left) does
			inOrderPushLeftChildsToStack(s, t);	
		}
	}

	// it does what inOrderRecursive(n.left) was doing
	public void inOrderPushLeftChildsToStack(Stack<Object> s, Node n) {
		while (n != null) {
			s.push(n);
			n = n.left;
		}
	}
	
	public void process(Node n) {
		System.out.println(n.data);
	}

}

3 comments:

  1. Good one.. But, on inOrderRecursive method since you already make a null check and return, is it necessary to make multiple null check on each recursive call?

    ReplyDelete
  2. Why you have specified the complexity as O(nlogn) whereas the complexity should be O(n) ?

    ReplyDelete