Lets say the in-order traversal is O = O1,O2,...On Pre-order is P = P1,P2,...Pn
Lets assume that the in-order traversal gives sorted sequence of numbers. (if not, we can replace Pi by i in our algorithm and replace it to original later on) Observe P1 will be the root. If left subtree is not empty, then P2 is the root of left subtree. Otherwise it is the root of right subtree. If left subtree is non empty, how can we find what is the root of right subtree? A[i,j] - returns pointer to root of the tree containing elements from Pi to Pj in order as we want them in our resultant tree. Algorithm - A[i,j,r1,r2] IF i==j return Pi ELSE 1. make Pi the root. 2. Binary search in P[i+1,j] to find out the last element Pk which is on left side of Pi in O[r1,r2] where Or = Pi. 3.a. if(!k) S1 = empty S2 = A[2,n,r1,r1,r-1] 3.b . else S1 = A[2,k], S2 = A[k+1,n,r+1,r2] 4. make S1 left child of P1 and S2 the right child of P1. Rec for running time T(n) = 2*T(n/2) + O(logn) It is linear. On Sun, Nov 27, 2011 at 8:26 PM, bharath sriram <bharath.sri...@gmail.com>wrote: > The in-order and pre-order traversal are already given. So, there is no > way to do what you are saying if I understand you completely. > > > On Sun, Nov 27, 2011 at 8:19 AM, Ankuj Gupta <ankuj2...@gmail.com> wrote: > >> Hint : try with prestoring the preorder traversal element position in >> inorder traversal before constructing the 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. > -- Nitin Garg "Personality can open doors, but only Character can keep them open" -- 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.
