Dec 28, 2008

Given a BST (Binary search Tree) how will you find median in that?

Given a BST (Binary search Tree) how will you find median in that?

Use two pointers p1 and p2
in order to traverse the tree
P1 forward 1 step, p2 forward 2 steps,
When p2 finish traversal, p1 point to the median
Or
Two pointers, p1 and p2
P1 traverse with left most in order
P2 traverse with right most in order
If p1 encounter p2, them point to median

No comments:

Post a Comment