CODEWITHSUNDEEP
performancealgorithmbinary-search-tree
Kaa1el
Kaa1el

Reputation: 337

Finding smallest (or largest) k elements in a given balanced binary search tree

Given a balanced binary search tree with integer nodes, I need to write an algorithm to find the smallest k elements and store them in a linked list or array. The tricky part is, it is required such algorithm runs in O(k+log(n)), where n is the number of elements in the tree. I only have an algorithm that runs O(k*log(n)), which uses the rank function. So my question is how to achieve the required performance?

I've written a code doing such algorithm but I don't know if it is running at O(k+log(n)):

(The size function is the number of nodes with the given subtree.)

// find k smallest elements in the tree
public Iterable<Key> kSmallest(int k) {
    LinkedList<Key> keys = new LinkedList<Key>();
    kSmallest(k, root, keys);
    return keys;
}

// find k smallest elements in the subtree given by node and add them to keys
private void kSmallest(int k, Node node, LinkedList<Key> keys) {
    if (k <= 0 || node == null) return;
    if (node.left != null) {
        if (size(node.left) >= k) kSmallest(k, node.left, keys);
        else {
            keys.add(node.key);
            kSmallest(k - 1, node.left, keys);
            kSmallest(k - 1 - size(node.left), node.right, keys);
        }
    }
    else {
        keys.add(node.key);
        kSmallest(k - 1, node.right, keys);
    }
}

Upvotes: 2

Views: 1728

Answers (1)

azero0
azero0

Reputation: 2310

Just have to to a inorder traversal and stop when you have gone through k nodes. this would run in O(k+log(n)) time.

code:

int k = nodesRequired;
int A[] = new int[k];
int number_of_nodes=0;
void traverse_tree(tree *l){
    if (number_of_nodes<k) {
        traverse_tree(l->left);
        process_item(l->item);
        traverse_tree(l->right);
    }
 }

 void process_item(item){
     A.push(item);
     ++number_of_nodes;
 }

Upvotes: 3

Related Questions