Sunday, September 18, 2011

Pre-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)

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

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

/**
 ** Given a binary search tree  
.
       4 
      / \ 
     2   5 
    / \ 
   1   3
  / 
0.5
 
** Produces the output "4 2 1 0.5 3 5". 

** http://codepad.org/QEVUNzYU
**/

public class PreOrder {
	
	
	/** ************************** PreOrder : Recursive ************************** **/

	public void preOrderRecursive(Node node) {
		
		if (node == null)
			return;
		
		// first deal with the node
		System.out.print(node.data);

		// then recur on both subtrees
		preOrderRecursive(node.left);
		preOrderRecursive(node.right);

	}
	
	/** ************************** PreOrder : Iterative ************************** **/

	
	public void preOrderIterative (Node n) {
		
		//using stack
		Stack<Object> s = new Stack<Object>();
		
		// what preOrderRecursive(n.left) does
		preOrderpPushLeftChildsToStack(s, n);

		// what happens when preOrderRecursive(n.right) is called
		while (!s.isEmpty()) {
			
			Node t = (Node) s.pop();
			
			// preOrderRecursive(n.right) is called
			t = t.right;
			// what preOrderRecursive(n.left) does
			preOrderpPushLeftChildsToStack(s, t);	
		}
	}
	
	// it does what preOrderRecursive(n.left) was doing
	// note - in preorder - the processing of node is done as soon as it is discovered.
	public void preOrderpPushLeftChildsToStack(Stack<Object> s, Node n) {
		while (n != null) {
			
			// processing on a node
			process(n);
			
			s.push(n);
			n = n.left;
		}
	}
	
	public void process(Node n) {
		System.out.println(n.data);
	}

}

6 comments:

  1. I disagree with the complexity conclusion. Since tree traversals visit each tree node only one time, time complexity must be linear in respect to the size of the tree.

    Isn't so?

    ReplyDelete
  2. Given information was very excellent & Great tips, and awesome way to get

    exert tips from everyone,not only i like that post all peoples like that

    post,because of all given information was wonderful and it's very helpful

    for me... SAP Training in Chennai

    ReplyDelete
  3. Being new to the blogging world I feel like there is still so much to learn. Your tips helped to clarify a few things for me as well as giving..
    iOS Training in Chennai
    Android Training in Chennai
    php Training in Chennai

    ReplyDelete
  4. I just see the post i am so happy to the communication science post of information's.So I have really enjoyed and reading your blogs for these posts.Any way I’ll be replay for your great thinks and I hope you post again soon...
    Java Training in Chennai

    ReplyDelete
  5. Thank you a lot for providing individuals with a very spectacular possibility to read critical reviews from this site.

    Android Training in Bangalore

    ReplyDelete