Facebook Interview Question: How do you find the kth small... | Glassdoor

Interview Question

Software Engineer Interview

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


Interview Answer

5 Answers


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

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

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

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

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

    if(temp) return temp;

    return NULL;

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

Anonymous on Nov 13, 2014

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