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);
	}

}

14 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
    Replies
    1. Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a Java developer learn from Java Training in Chennai. or learn thru Java Online Training India . Nowadays Java has tons of job opportunities on various vertical industry.

      Delete
  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
  6. I am really very happy to find this particular site. I just wanted to say thank you for this huge read!! I absolutely enjoying every petite bit of it and I have you bookmarked to test out new substance you post.

    python training in chennai | python training in bangalore

    python online training | python training in pune

    python training in chennai | python training in bangalore

    python training in tambaram | python training in velachery

    ReplyDelete
  7. Thanks for the good words! Really appreciated. Great post. I’ve been commenting a lot on a few blogs recently, but I hadn’t thought about my approach until you brought it up. 
    java training in omr

    java training in annanagar | java training in chennai

    java training in marathahalli | java training in btm layout

    java training in rajaji nagar | java training in jayanagar

    ReplyDelete
  8. A universal message I suppose, not giving up is the formula for success I think. Some things take longer than others to accomplish, so people must understand that they should have their eyes on the goal, and that should keep them motivated to see it out til the end.
    Data Science with Python training in chenni
    Data Science training in chennai
    Data science training in velachery
    Data science training in tambaram
    Data Science training in OMR
    Data Science training in anna nagar
    Data Science training in chennai
    Data science training in Bangalore

    ReplyDelete
  9. Inspiring writings and I greatly admired what you have to say , I hope you continue to provide new ideas for us all and greetings success always for you..Keep update more information..

    rpa training in Chennai

    rpa training in anna nagar | rpa training in marathahalli

    rpa training in btm | rpa training in kalyan nagar

    rpa training in electronic city | rpa training in chennai

    rpa online training | selenium training in training

    ReplyDelete
  10. Inspiring writings and I greatly admired what you have to say , I hope you continue to provide new ideas for us all and greetings success always for you..Keep update more information..
    python online training
    python training in OMR
    python training in tambaram

    ReplyDelete
  11. Very good brief and this post helped me alot. Say thank you I searching for your facts. Thanks for sharing with us!
    Devops training in sholinganallur
    Devops training in velachery

    ReplyDelete
  12. Hmm, it seems like your site ate my first comment (it was extremely long) so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog. I as well as an aspiring blog writer, but I’m still new to the whole thing. Do you have any recommendations for newbie blog writers? I’d appreciate it.

    Best Selenium Training in Chennai | Selenium Training Institute in Chennai | Besant Technologies

    Selenium Training in Bangalore | Best Selenium Training in Bangalore

    AWS Training in Bangalore | Amazon Web Services Training in Bangalore

    ReplyDelete