Interview Question

Software Engineer Interview

How do you find the kth smallest number in a binary search

  tree.
Answer

Interview Answer

5 Answers

0

A brute force approach would be to put all the left children in an array and then look for kth element of this array.

Lucas on May 28, 2014
3

Inorder traversal the tree, the returned array is sorted, then find the Kth smallest number. O(n)time and O(n)space.Anyone has better idea?

Anonymous on May 31, 2014
3

Inorder traversal, but count the number of the nodes you visted, because the visiting order will just be increasing,so O(lgn) time to find the smallest node and O(1) space to store counter.

Anonymous on Jun 9, 2014
0

int k = 0;
node* kthLastNodeBST(node *root)
{
    if (root == NULL)
        return NULL;

    node *temp = kthLastNodeBST(root->left);
    if(temp) return temp;

    k--;
    if(k<=0)
        return root;

    temp = kthLastNodeBST(root->right);
    if(temp) return temp;

    return NULL;
}

k =3;
node *temp = kthLastNodeBST(root);

Anonymous on Nov 13, 2014
0

Add an integer variable to the Tree Node - numNodesLeft to keep a count of number of nodes in the left subtree of current node. This is O(lg(n))
public KBSTNode kthSmallest(KBSTNode root, int k) {
        if(root==null || k<=0) {
            return null;
        }
        if(root.numNodesLeft==k-1) {
            return root;
        }
        if(root.numNodesLeft>=k) {
            return kthSmallest(root.left,k);
        }
        return kthSmallest(root.right,k-root.numNodesLeft-1);
    }

GReeky on Jan 11, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.