median in a BST
how to find a median in BST?One way is traverse inorder and return the middle element. This takes O(n) for traversal, O(n) extra space and O(1) for finding the median. suggest any solution that takes o(n) for traversal but constant space?
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/ .
ReplyDelete