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.
