Cracking The Code.Did You Know Efficient & Working Code Really Matters: 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.

Monday, October 31, 2011

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.

2 comments:

KarthickOctober 31, 2011 at 9:00 PM
Assuming that every node has parent pointer, we can perform left or right rotation(depending on whether the node is right or left child)until we reach the root.

Is this correct?
ReplyDelete
Replies
sreekarNovember 2, 2011 at 8:33 AM
Perform an inorder traversal and find the given node in it and keep the given node as root and insert the nodes to it in the given inorder traversal.

This will take O(N log N)

I believe there will be a better solution similar to AVL Tree rotation
ReplyDelete
Replies

Hi thanks , we will get back to you shortly !!!