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)


import java.util.Stack;

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


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

	public void preOrderRecursive(Node node) {
		if (node == null)
		// first deal with the node

		// then recur on both subtrees

	/** ************************** 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
			n = n.left;
	public void process(Node n) {



  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?

  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

    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.

  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

  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

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

    Android Training in Bangalore

  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

  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

  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

  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

  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

  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

  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

  13. Thank you for benefiting from time to focus on this kind of, I feel firmly about it and also really like comprehending far more with this particular subject matter. In case doable, when you get know-how, is it possible to thoughts modernizing your site together with far more details? It’s extremely useful to me.
    devops online training

    aws online training

    data science with python online training

    data science online training

    rpa online training

  14. thanks for Sharing such an Awesome information with us.

    I learned World's Trending Technology from certified experts for free of cost.i Got job in decent Top MNC Company with handsome 14 LPA salary, i have learned the World's Trending Technology from Python training in pune experts who know advanced concepts which can helps to solve any type of Real time issues in the field of Python. Really worth trying Freelance seo expert in bangalore

  15. Attend The Data Analytics Course in Bangalore From ExcelR. Practical Data Analytics Course in Bangalore Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analytics Course in Bangalore.
    ExcelR Data Analytics Course in Bangalore

  16. Very awesome!!! When I seek for this I found this website at the top of all blogs in search engine.
    learn 360digitmg ai courses

  17. It is perfect time to make some plans for the future and it is time to be happy. I've read this post and if I could I desire to suggest you some interesting things or suggestions. Perhaps you could write next articles referring to this article. I want to read more things about it! PMP Certification 360DigiTMG
    PMP Course 360DigiTMG
    PMP Course in Malaysia 360DigiTMG
    PMP Training 360DigiTMG
    PMP Training in Malaysia 360DigiTMG

  18. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
    data analytics course
    big data analytics malaysia
    big data course

  19. Great Information sharing .. I am very happy to read this article .. thanks for giving us go through info.Fantastic nice. I appreciate this science course