@Ankuj: Your method would be O(n), where n is the number of nodes in the tree. However, it can be done with a sequence of tree rotations. If the desired node is not the root of the tree, rotate it with its parent. This preserves the BST property and makes the desired node one level closer to the root. A rotation can be done in constant time, so the work required is O(original level of the node), which would be O(log n) if the tree happened to be balanced. See http://en.wikipedia.org/wiki/Tree_rotation for algorithmic details.
Dave On Oct 31, 11:43 am, Ankuj Gupta <[email protected]> wrote: > Given a node of a BST, modify it in such a way that the given node > becomes the root. The tree should still be BST. One way I could get is > store the Inoder traversal of the tree. Find that node in the > traversal and recursively make the BST. -- 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.
