Solved

BST

Posted on 2007-11-17
12
387 Views
Last Modified: 2010-04-01
How do i construct BST based on the following:
12, 11, 8, 16, 5, 7, 13, 9, 2

I have been thinking about this for quite some time. Inorder traversal is not suitable as it returns a list of ascending numbers. I have also tried preorder and postorder traversal....but it doesn't seem to work. Pls help.

I just need a diagram to illustrate the BST.
0
Comment
Question by:dandeliondream
  • 5
  • 4
  • 2
  • +1
12 Comments
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 20306857
Have a look to this tutorial:
http://en.wikipedia.org/wiki/Binary_search_tree
0
 
LVL 3

Author Comment

by:dandeliondream
ID: 20306900
i think it shld be a preorder since postorder and inorder starts with 2. right? i have seen the tutorial.. :( not very useful pls help
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 50 total points
ID: 20306905
Depending on what you mean by "based" it could be
                   12  
           11             16
       8                13
   5      9
2   7
0
 
LVL 55

Assisted Solution

by:Jaime Olivares
Jaime Olivares earned 50 total points
ID: 20306928
I have not clear your question.
Traversal is done AFTER tree is created. Tree internal shape will depend how you have inserted the nodes into it.
In-order traversal will always give you an ordered result.
pre-order and post-order will give you "unordered" result but exact sequence will depend on internal shape.
0
 
LVL 3

Author Comment

by:dandeliondream
ID: 20306948
12, 11, 8, 16, 5, 7, 13, 9, 2 is the sequence from left to right after a traversal is done. It may be preorder, postorder or inorder traversal. Based on the sequence, how can i construct a BST?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20307196
You want to store the values 12, 11, 8, 16, 5, 7, 13, 9, 2 in a BST in that exact order ? Why use a BST then ? Why not just an array or a vector ?

There's no point. A BST's strength is that it makes searching of an ORDERED series a lot faster. You'd have to add a second index value that acts as key into the BST, and store the value as data. Sounds a bit overkill to me. Just take an array or vector.
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 3

Author Comment

by:dandeliondream
ID: 20307319
no that's not what i meant. I want a diagram like what mr. ozo has given me earlier. Construct a BST based on the list of numbers The numners are to be processed from left to right.
12, 11, 8, 16, 5, 7, 13, 9, 2

Not a program. Just a diagram.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20307322
Yes, but there's two orders :

1) the order you put the values into the BST
2) the order you get them out of the BST

Which are you referring to when you want to get this order : 12, 11, 8, 16, 5, 7, 13, 9, 2 ?
0
 
LVL 3

Author Comment

by:dandeliondream
ID: 20307390
the second one...
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20307393
>> the second one...

Then I repeat : there's no point in using a BST - just use a simple array or vector.
0
 
LVL 3

Author Comment

by:dandeliondream
ID: 20307432
ok, thanks. what will the result be if it is the first one?
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 150 total points
ID: 20307438
>> ok, thanks. what will the result be if it is the first one?

A BST that looks like what ozo showed. You can of course balance the tree out, but you will not be able to get the values out the same order you put them in there (unless by chance).
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Least Squares Curve Fitting 4 61
Header of docx file 17 98
Tembedded WB animatid gifs not animated on some pcs 2 73
Copy output image from TWindowsMediaPlayer 6 23
Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may he…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

920 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now