Re: [algogeeks] Reconstruct BST from preorder traversal
@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 this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/7Debg9dGk2UJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reconstruct BST from preorder traversal
On Tue, Oct 18, 2011 at 6:30 PM, sravanreddy001 wrote: > 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 given. and u have to give a generalise approach which could be applied to any preorder array. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/3TnK7Rk4vtcJ. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Regards, Rahul Patil -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reconstruct BST from preorder traversal
@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 Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reconstruct BST from preorder traversal
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 discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/3TnK7Rk4vtcJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reconstruct BST from preorder traversal
@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 sorted one, so possible solution could be any BST containing all the elements in the preorder array. On Tue, Oct 18, 2011 at 1:41 PM, anshu mishra wrote: > @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 from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards, Rahul Patil -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reconstruct BST from preorder traversal
@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 from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reconstruct BST from preorder traversal
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 = ar[s];
root->left = root->right = NULL;
int mid = find_mid(ar, s+1, e, ar[s]);
if (s+1 < mid)
root -> left = constructTree(ar, s+1, mid);
if (mid < e)
root -> right = constructTree(ar, mid, e);
return root;
}
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reconstruct BST from preorder traversal
You will also need Inorder traversal data. On Tue, Oct 18, 2011 at 10:12 AM, Ankuj Gupta 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 post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reconstruct BST from preorder traversal
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 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 post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Reconstruct BST from preorder traversal
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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
