dandeliondream
asked on
BST
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.
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.
ASKER
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
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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?
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.
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.
ASKER
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.
12, 11, 8, 16, 5, 7, 13, 9, 2
Not a program. Just a diagram.
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 ?
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 ?
ASKER
the second one...
>> the second one...
Then I repeat : there's no point in using a BST - just use a simple array or vector.
Then I repeat : there's no point in using a BST - just use a simple array or vector.
ASKER
ok, thanks. what will the result be if it is the first one?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
http://en.wikipedia.org/wiki/Binary_search_tree