1. Give pseudocode for an algorithm that accepts a BST node and an integer k and

Question

1. Give pseudocode for an algorithm that accepts a BST node and an integer k and retuns ethsmaes element in the BST rooted at that node. For example, the tree rooted at node A below contains the values 5, 10, 15, 20, and 25. The 4th smallest element in this tree is 20, so the problem instance with node A and k = 4 should return 20. 20 10 25 15 The behavior of the algorithm is undefined if k is too small or too large; e.g., calling the algorithm with k =-1 can return anything. In adlition to the usual value, left, right, and parent fields, the BST nodes have a count feld that stores the number of nodes in the tree rooted at this node. The count values appear in te diagram as small numbers below each node. Hint: I recommend a recursive algorithm

Explanation / Answer

Here's just an outline of the idea:

In a BST, the left subtree of node T contains only elements smaller than the value stored in T. If k is smaller than the number of elements in the left subtree, the kth smallest element must belong to the left subtree. Otherwise, if k is larger, then the kth smallest element is in the right subtree.

We can augment the BST to have each node in it store the number of elements in its left subtree (assume that the left subtree of a given node includes that node). With this piece of information, it is simple to traverse the tree by repeatedly asking for the number of elements in the left subtree, to decide whether to do recurse into the left or right subtree.

Now, suppose we are at node T:

Complexity analysis:

This takes O(depth of node) time, which is O(log n) in the worst case on a balanced BST, or O(log n) on average for a random BST.

A BST requires O(n) storage, and it takes another O(n) to store the information about the number of elements. All BST operations take O(depth of node) time, and it takes O(depth of node) extra time to maintain the "number of elements" information for insertion, deletion or rotation of nodes. Therefore, storing information about the number of elements in the left subtree keeps the space and time complexity of a BST.

In case, If you want to find the smallest number under a root node in a BST then, The idea is to use Morris Traversal. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.

Below is the implementation in c++ which finds out the smallest number under root node. you just need to modify the location of root and point it to the desired node whoose smallest number you want to find.

THE C++ implementation of the idea.

// C++ program to find k'th largest element in BST
#include<iostream>
#include<climits>
using namespace std;

// A BST node
struct Node
{
   int key;
   Node *left, *right;
};

// A function to find
int KSmallestUsingMorris(Node *root, int k)
{
   // Count to iterate over elements till we
   // get the kth smallest number
   int count = 0;

   int ksmall = INT_MIN; // store the Kth smallest
   Node *curr = root; // to store the current node

   while (curr != NULL)
   {
       // Like Morris traversal if current does
       // not have left child rather than printing
       // as we did in inorder, we will just
       // increment the count as the number will
       // be in an increasing order
       if (curr->left == NULL)
       {
           count++;

           // if count is equal to K then we found the
           // kth smallest, so store it in ksmall
           if (count==k)
               ksmall = curr->key;

           // go to current's right child
           curr = curr->right;
       }
       else
       {
           // we create links to Inorder Successor and
           // count using these links
           Node *pre = curr->left;
           while (pre->right != NULL && pre->right != curr)
               pre = pre->right;

           // building links
           if (pre->right==NULL)
           {
               //link made to Inorder Successor
               pre->right = curr;
               curr = curr->left;
           }

           // While breaking the links in so made temporary
           // threaded tree we will check for the K smallest
           // condition
           else
           {
               // Revert the changes made in if part (break link
               // from the Inorder Successor)
               pre->right = NULL;

               count++;

               // If count is equal to K then we found
               // the kth smallest and so store it in ksmall
               if (count==k)
                   ksmall = curr->key;

               curr = curr->right;
           }
       }
   }
   return ksmall; //return the found value
}

// A utility function to create a new BST node
Node *newNode(int item)
{
   Node *temp = new Node;
   temp->key = item;
   temp->left = temp->right = NULL;
   return temp;
}

/* A utility function to insert a new node with given key in BST */
Node* insert(Node* node, int key)
{
   /* If the tree is empty, return a new node */
   if (node == NULL) return newNode(key);

   /* Otherwise, recur down the tree */
   if (key < node->key)
       node->left = insert(node->left, key);
   else if (key > node->key)
       node->right = insert(node->right, key);

   /* return the (unchanged) node pointer */
   return node;
}

// Driver Program to test above functions
int main()
{
   /* Let us create following BST
           50
       /  
       30   70
       / /
   20 40 60 80 */
   Node *root = NULL;
   // to find the smallest number below desired root modify the root loation
   root = insert(root, 50);
   insert(root, 30);
   insert(root, 20);
   insert(root, 40);
   insert(root, 70);
   insert(root, 60);
   insert(root, 80);

cout<<KSmallestUsingMorris(root, 3) << " ";

   return 0;
}

OUTPUT:

40

here 40 is the 3rd smallest number in the BST under root node.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.