Question

Show how to augment the ordinary Binary Search Tree (BST) data structure so that it supports an efficient procedure which, on input (x, k) where x is the root of a BST and k an integer, output the k-th smallest number store in the BST. Let n denote the total number of elements stored in the BST, what is the running time of your efficient procedure? How does your modification of the BST data structure affect the performance of other BST operations we discussed in class?

Answer 1

In the following BST, if k = 3, then the output should be 10, and if k = 5, then the output should be 14.
Using Inorder Traversal

left subtree,root rigt subtree

Node

struct Node {

    int data;

    Node *left, *right;

    Node(int x)

    {

        data = x;

        left = right = NULL;

    }

};

Node* insert(Node* root, int x)

{

    if (root == NULL)

        return new Node(x);

    if (x < root->data)

        root->left = insert(root->left, x);

    else if (x > root->data)

        root->right = insert(root->right, x);

    return root;

}

Node* kthSmallest(Node* root, int k)

{

    if (root == NULL)

        return NULL;

    int count = root->lCount + 1;

    if (count == k)

        return root;

    if (count > k)

        return kthSmallest(root->left, k);

    return kthSmallest(root->right, k - count);

}

int main()

{

    Node* root = NULL;

    int keys[] = { 20, 8, 22, 4, 12, 10, 14 };

    for (int x : keys)

        root = insert(root, x);

    int k = 4;

    Node* res = kthSmallest(root, k);

    if (res == NULL)

        cout << "There are less than k nodes in the BST";

    else

        cout << "K-th Smallest Element is " << res->data;

    return 0;

}

Ans:

K-th Smallest Element is:12