hey,i guess a specific binary tree is not possible...by d use of jst a
preorder...
4 a specific tree inorder is also reqd...
dere will be many trees posible...sso is it dat v got 2 make all possible
tree vth d given preorder???
On Tue, Oct 18, 2011 at 10:12 AM, Ankuj Gupta ankuj2...@gmail.com
this is an O(n^2) solution. By pre processing the array we can also solve it
O(n)
int find_mid(int ar[], int s, int e, int val)
{
int i;
for (i = s; ar[i] val; i++);
return i;
}
node * constructTree(int ar[], int s, int e)
{
node *root;
root = new node();
root-val =
You will also need Inorder traversal data.
On Tue, Oct 18, 2011 at 10:12 AM, Ankuj Gupta ankuj2...@gmail.com wrote:
How to reconstruct a BST from just the prorder traversal of that tree ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
@Anand
As given it is a BST so any single traversal(pre or post or in) is
sufficient to construct the tree. :P
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe
@Anshu: for a tree
15
15
7 18and
717
17 18
inorder traversal is same: 7,15,17,18
then how it could be possible to recreate the specific one. Preorder of BST
is
This might sound silly. But I have a doubt here.when you mean convert inorder
or preorder to a bst. Are the inorder traversel elements given and we need to
construct a bst?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this
@sravan
yes you are given the sequence of elements in the order in which they are
traversed in the given traversal (in/pre/post)
a BST can be constructed from its post or pre order only but can not be
constructed from only inorder
in case of inorder we also need one more traversal
--
Sunny
On Tue, Oct 18, 2011 at 6:30 PM, sravanreddy001 sravanreddy...@gmail.comwrote:
This might sound silly. But I have a doubt here.when you mean convert
inorder or preorder to a bst. Are the inorder traversel elements given and
we need to construct a bst?
Yes inorder traversal elements are
@Sunny, Rahul:
Thanks a lot.. :)
@Anshu: the code is perfect, This would be h = n* (height of BST) -- O(h)
O(n^2) is the worst case right? and has complexity similar to quick sort?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view
How to reconstruct a BST from just the prorder traversal of that tree ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
10 matches
Mail list logo