A[1,n,1,n] will give us the solution. On Mon, Nov 28, 2011 at 7:47 PM, Nitin Garg <nitin.garg.i...@gmail.com>wrote:
> 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" > -- 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.
