thanks all On Wed, Jul 4, 2012 at 10:57 PM, Navin Gupta <[email protected]> wrote:
> Given a pre-order traversal, we can sort it to get the inorde traversal. > Sorting the preorder is O( NLogN ). > Now as we know the ordering of elements is > Preorder -> Root -> Left Child -> Right Child > Inorder -> Left Child -> Root -> Right Child > 1>The first element in Pre-order traversal is root of tree. > 2>find its index in the inorder traversal ( I ) . > 3>All the elements to the left of root in inorder traversal consist > Left-Subtree ( IL ) of the root while those to the right consist > Right-Subtree ( IR ) of the root. > 4>Perform the steps 1-3 recursively for the IL & IR. > Searching is LogN, so constructing the entire tree is O(NLogN). > Even though we can use hash to get O(1) search complexity. But still > sorting the preorder to get inorder is O ( NLogN ). > > -- > Navin Kumar Gupta > Final Year,B.Tech(Hons.) > Computer Science & Engg. > National Institute of Technology,Jamshedpur > Mobile - (+91)8285303045 > > -- > 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/-/wmkx-kDe3EEJ. > > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Vindhya Chhabra -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
