## 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".

**/

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

}

```

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. Cool stuff you have and you keep overhaul every one of us

data scientist course

data analytics

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

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

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

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