Given a binary search tree. Find the kth smallest element in the BST.
A quick solution would be to perform a modified inorder traversal with an extra parameter k. Each time inorder traversal is popping a node out of recursion/call stack (i.e. unwinding a recursion)then we keep decreasing the k. When k=0 then the current node in the call stack is the desired kth smallest node. This is O(n) time algorithm.
For example, for the following BST the nodes in inorder traversal are: 1, 2. 3, 4, 5, 6. So, the 3rd smallest is 3.
4 / \ 2 5 / \ \ 1 3 6
However with some augmented data in our tree and doing some inexpensive bookkeeping during build up of the tree, we can find kth smallest in O(lgn) time. Observe that,
Number of smaller nodes than a node is equal to the size of the left subtree.
This leads us to assign rank to each of the node. Notice that
size(node) = size(node.left)+size(node.right)+1; rank(node) = size(node.left)+1
So, we can either update the size left subtree of each node during building phase of the tree or during a later phase. Now it would be easy to find kth smallest using a binary search on the tree using the fact that the kth smallest element has rank of k. If the middle element's rank is less than k then we search only in left subtree or vice versa. Below is the O(lgn) implementation of this idea with the BST augmented with size and updating the size during each insert:
Read full article from Kth smallest/minimum element in a BST - Rank of a BST node - Algorithms and Problem SolvingAlgorithms and Problem Solving
No comments:
Post a Comment