Thursday, February 10, 2011

Find K-th smallest element in a binary search tree (BST)

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).

No comments: