@Dave : Wonderful answer sir.. On 31 October 2011 12:50, Dave <[email protected]> wrote:
> @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. > > -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, [email protected] -- 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.
