{"id":27375,"date":"2018-02-02T20:54:39","date_gmt":"2018-02-02T15:24:39","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27375"},"modified":"2018-02-02T20:54:39","modified_gmt":"2018-02-02T15:24:39","slug":"c-program-kth-smallest-element-bst-using-o1-extra-space","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-program-kth-smallest-element-bst-using-o1-extra-space\/","title":{"rendered":"C++ Program-K\u2019th smallest element in BST using O(1) Extra Space"},"content":{"rendered":"

Given a Binary Search Tree (BST) and a positive integer k, find the k\u2019th smallest element in the Binary Search Tree.<\/span><\/p>\n

For example, in the following BST, if k = 3, then output should be 10, and if k = 5, then output should be 14.<\/p>\n

We have discussed two methods in this <\/a>post and one method in this <\/a>post. All of the previous methods require extra space. How to find the k\u2019th largest element without extra space?<\/p>\n

We strongly recommend to minimize your browser and try this yourself first.<\/strong>Implementation<\/strong><\/p>\n

The idea is to use Morris Traversal<\/a>. 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. See this <\/a>for more details.<\/p>\n

Below is C++ implementation of the idea.<\/p>\n

C++ Programming<\/span> <\/div> 
\/\/ C++ program to find k'th largest element in BST#include<iostream>#include<climits>using namespace std; \/\/ A BST nodestruct Node{    int key;    Node *left, *right;}; \/\/ A function to findint 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 nodeNode *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 functionsint main(){    \/* Let us create following BST              50           \/     \\          30      70         \/  \\    \/  \\       20   40  60   80 *\/    Node *root = NULL;    root = insert(root, 50);    insert(root, 30);    insert(root, 20);    insert(root, 40);    insert(root, 70);    insert(root, 60);    insert(root, 80);     for (int k=1; k<=7; k++)       cout << KSmallestUsingMorris(root, k) << " ";     return 0;}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Output:<\/strong><\/p>\n
20 30 40 50 60 70 80<\/pre>\n","protected":false},"excerpt":{"rendered":"
K\u2019th smallest element in BST using O(1) Extra Space – Binary Search Tree – Given a Binary Search Tree (BST) and positive integer k, find the k\u2019th smallest.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80126,83515],"tags":[81505,81338,81507,81334,81337,81331,81335,81332,81506,81333,81330],"class_list":["post-27375","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree","category-c-programming-3","tag-2-sum-binary-tree","tag-algorithm-to-find-pair-of-numbers-whose-sum-is-equal-to-k","tag-c-program-kth-smallest-element-in-bst-using-o1-extra-space","tag-find-the-second-largest-element-in-a-binary-search-tree","tag-given-an-array-and-a-number-k","tag-kth-largest-element-in-bst-java","tag-kth-smallest-element-in-a-array","tag-kth-smallest-element-in-a-bst-c","tag-kth-smallest-element-in-a-bst-leetcode-c","tag-kth-smallest-element-in-a-bst-recursive","tag-kth-smallest-element-in-bst-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27375","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27375"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27375\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27375"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27375"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}