# Binary Search Tree's Sorting

This topic is 4599 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

i would like to ask if i want to sort a set of number.. let's say n. By constructing those numbers into a binary tree then do in-order walk to print them.. wut would be the best-case and worst-case running times?

##### Share on other sites
This sounds like homework, which means you can ask for help but not for answers

##### Share on other sites
Quote:
 Original post by ExtrariusThis sounds like homework, which means you can ask for help but not for answers

i did it myself once.. but not sure if i am correct
i found it to be (nlgn) and (n^2) for best and worst.

but to my understanding..
constructing a binary tree = O(nlgn)
in-order-walk = O(n)

shouldnt it be O(n(1+lgn))

##### Share on other sites
When two terms are added, if you take the limit going to infinity, one of them will be much larger than the other. That is the whole idea of asymptotic notation, and when comparing "n" to "n*log(n)", the latter will be far larger with huge numbers and is thus the only one considered.

##### Share on other sites
Quote:
 Original post by ExtrariusWhen two terms are added, if you take the limit going to infinity, one of them will be much larger than the other. That is the whole idea of asymptotic notation, and when comparing "n" to "n*log(n)", the latter will be far larger with huge numbers and is thus the only one considered.

o.. really...
so. just take o(nlgn) as the best case?

if so.. for the worst case:
since.. worst time for contructing a binary tree would be n^2
and so it would be n + n^2 => O(n^2)
rite?

Yes[smile]

1. 1
Rutin
67
2. 2
3. 3
4. 4
5. 5

• 21
• 10
• 33
• 20
• 9
• ### Forum Statistics

• Total Topics
633420
• Total Posts
3011790
• ### Who's Online (See full list)

There are no registered users currently online

×