11, Feb 2011
The question related to order statistics. A BST (non-linear data structure) represents data in an order fashion that satisfies the binary search tree property of "left node key should be <= root and right node key should be >= root".
Since we need K-th smallest element, we need to maintain # of elements in either of the sub-trees. By maintaining the count we can get the sub tree nodes in O(1) time complexity.
Assume the root has n nodes in its left subtree. If n <= K, we will continue search (recursion) for the smallest element in the left subtree. If K = n + 1, the root has the K-th smallest element. If k > n + 1, then we continue search the right subtree for the (K - n- 1)-th smallest element.
There are other approaches, like inorder traversal by maintaining the count, and stop search at K-th element or trivial case of no K-th node.
I have published two approaches for finding k-th smallest element in BST (See the link).
The question related to order statistics. A BST (non-linear data structure) represents data in an order fashion that satisfies the binary search tree property of "left node key should be <= root and right node key should be >= root".
Since we need K-th smallest element, we need to maintain # of elements in either of the sub-trees. By maintaining the count we can get the sub tree nodes in O(1) time complexity.
Assume the root has n nodes in its left subtree. If n <= K, we will continue search (recursion) for the smallest element in the left subtree. If K = n + 1, the root has the K-th smallest element. If k > n + 1, then we continue search the right subtree for the (K - n- 1)-th smallest element.
There are other approaches, like inorder traversal by maintaining the count, and stop search at K-th element or trivial case of no K-th node.
I have published two approaches for finding k-th smallest element in BST (See the link).
No comments:
Post a Comment