Constraints:
- No extra memory.
- Algorithm should be efficient in terms of complexity.
----------------------------------------------------
No extra memory is allowed, so we can't use recursive tree traversal.
We can find the median by using the rabbit and the turtle pointer. The rabbit moves twice as fast as the turtle in the in-order traversal of the BST. This way when the rabbit reaches the end of traversal, the turtle in at the median of the BST. Please see the full expalaination at http://www.technicallyidle.com/2011/01/05/median-of-a-binary-seach-tree-bst/ .
1) Use Morris Traversal (http://geeksforgeeks.org/?p=6358) to get the number of nodes in BST. Let number of nodes be n.
2) Traverse till the n/2the node using Morris traversal again.
3) Print the middle node.
We can find the median by using the rabbit and the turtle pointer. The rabbit moves twice as fast as the turtle in the in-order traversal of the BST. This way when the rabbit reaches the end of traversal, the turtle in at the median of the BST. Please see the full expalaination at http://www.technicallyidle.com/2011/01/05/median-of-a-binary-seach-tree-bst/ .
♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥
http://geeksforgeeks.org/forum/topic/median-of-bst#post-643
No comments:
Post a Comment