{"id":1667,"date":"2024-02-04T01:00:00","date_gmt":"2024-02-04T01:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1667"},"modified":"2024-03-06T07:49:23","modified_gmt":"2024-03-06T07:49:23","slug":"kth-smallest-element-bst","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/kth-smallest-element-bst\/","title":{"rendered":"Find kth Smallest Element in BST (C++, Java, Python)"},"content":{"rendered":"\n

A binary search tree, or BST. stores the values in such a way that if we write the inorder of that tree it will be in ascending order. This can be achieved if the value of a left node is smaller and the value of the right node is greater or equal to the parent node. Different types of questions are asked in interviews based on BST, but we will discuss how to find the kth smallest element in the BST.<\/p>\n\n\n\n

What is the “kth Smallest element in the BST”?<\/strong><\/h2>\n\n\n\n

In this problem, you have to find the kth smallest element from a given binary search tree. K is always smaller or equal to the total number of nodes in the tree. Let’s look at an example to learn more.<\/p>\n\n\n\n

In the given tree the 3rd smallest element is 5.<\/p>\n\n\n

\n
\"Example\"\/<\/figure>\n<\/div>\n\n\n

The basic approach is to store the values of nodes in an array. Then sort the array and find the kth smallest value from this.<\/strong><\/p>\n\n\n\n

Let’s examine this with an example:<\/p>\n\n\n\n

\"Given<\/figure>\n\n\n\n

\u2022 Create an array <\/p>\n\n\n\n

\"Create<\/figure>\n\n\n\n

\u2022 Traverse each node in the tree and store their values in the array. <\/p>\n\n\n\n

\"Store<\/figure>\n\n\n\n

\u2022 Sort the array.<\/p>\n\n\n\n

\"Sort<\/figure>\n\n\n\n

\u2022 Return the value present at the k-1 index of the array.\u00a0<\/p>\n\n\n\n

The time complexity of the code is O( n log(n) ) where n is the total number of elements present in the array. This is because we are sorting the array and sorting required (n log(n)) time complexity. Space complexity is O(n) because we are using an array to store all the values of the tree.<\/p>\n\n\n\n

Inorder Traversal Approach to Find It\u00a0<\/strong><\/h2>\n\n\n\n

In the above approach, we are sorting the array which increases our time complexity to O( n log(n)). Also in the above approach space required is around O(n) which can be reduced if we use the inorder traversal.\u00a0<\/p>\n\n\n\n

The steps for the inorder traversal approach to find kth smallest element in BST are:<\/p>\n\n\n\n

    \n
  1. First, traverse the left node.<\/li>\n\n\n\n
  2. Update the current value of the count variable to count + 1.<\/li>\n\n\n\n
  3. If the value of count becomes equal to k then print this value and return. <\/li>\n\n\n\n
  4. If not go for the right node of the current node.<\/li>\n\n\n\n
  5. If at any point the node is Null then, return.<\/li>\n<\/ol>\n\n\n\n

    C++ Code<\/strong><\/h3>\n\n\n\n

    Here is the C++ program to find kth smallest element in BST:<\/p>\n\n\n\n

    #include <bits\/stdc++.h>\nusing namespace std;\n\n\nclass node{\n    public:\n    \n    int value;\n    node* left;\n    node* right;\n\n\n    node(){\n        left = NULL;\n        right = NULL;\n    }\n\n    node(int x){\n        value = x;\n        left = NULL;\n        right = NULL;\n    }\n};\n\n\/\/ variable that stores the kth smallest value\nint ans = -1;\n\n\/\/ function that is doing inorder traversal\nvoid fun(node* root, int& count, int k){\n    if(root==NULL) return ;\n\n    fun(root->left,count,k);\n    count++;\n   \n    if(count==k){\n        ans = root->value;\n        return;\n    }\n    fun(root->right,count,k);\n    return;\n}\n\nint main(){\n\n    \/\/ creating a tree \n\n        \/\/     5\n        \/\/    \/ \\\n        \/\/   3   7\n        \/\/  \/ \\   \\\n        \/\/ 1   4   9\n    \n    node* head = new node(5);\n    head->left = new node(3);\n    head->right = new node(7);\n    head->left->left = new node(1);\n    head->left->right = new node(4);\n    head->right->right =  new node(9);\n    \n    \/\/ k is 5, so the 5th smallest value is 7 here \n    \/\/ 1 -> 1\n    \/\/ 2 -> 3\n    \/\/ 3 -> 4\n    \/\/ 4 -> 5\n    \/\/ 5 -> 7\n    \/\/ 6 -> 9\n\n    int k = 5;\n    int count = 0;\n\n    fun(head,count,k);\n    \/\/ prints 7\n    cout<<k<<"th smallest values is: "<<ans<<endl;\n    return 0;\n}<\/pre><\/div>\n\n\n\n
    Java Code<\/strong><\/h3>\n\n\n\n
    Here is the Java program to find it:<\/p>\n\n\n\n
    class Node {\n    int value;\n    Node left, right;\n\n    Node(int x) {\n        value = x;\n        left = right = null;\n    }\n}\n\nclass KthSmallestValue {\n    \/\/ variable that store the kth smallest value\n    static int[] ans = {-1};\n\n    \/\/ function that is doing inorder traversal\n    static void fun(Node root, int[] count, int k) {\n        if (root == null)\n            return;\n\n        fun(root.left, count, k);\n        count[0]++;\n       \n        if (count[0] == k) {\n            ans[0] = root.value;\n            return;\n        }\n        fun(root.right, count, k);\n    }\n\n    public static void main(String[] args) {\n        \/\/ creating a tree \n        \/\/     5\n        \/\/    \/ \\\n        \/\/   3   7\n        \/\/  \/ \\   \\\n        \/\/ 1   4   9\n\n        Node head = new Node(5);\n        head.left = new Node(3);\n        head.right = new Node(7);\n        head.left.left = new Node(1);\n        head.left.right = new Node(4);\n        head.right.right =  new Node(9);\n        \n        \/\/ k is 5, so the 5th smallest is value is 7 here \n        \/\/ 1 -> 1\n        \/\/ 2 -> 3\n        \/\/ 3 -> 4\n        \/\/ 4 -> 5\n        \/\/ 5 -> 7\n        \/\/ 6 -> 9\n\n        int k = 5;\n        int[] count = {0};\n\n        fun(head, count, k);\n        \/\/ prints 7\n        System.out.println(k + "th smallest values is: " + ans[0]);\n    }\n}<\/pre><\/div>\n\n\n\n
    Python Code<\/strong><\/h3>\n\n\n\n
    You can do the same in Python also:<\/p>\n\n\n\n
    class Node:\n    def __init__(self, x):\n        self.value = x\n        self.left = None\n        self.right = None\n\n# variable that stores the kth smallest value\nans = [-1]\n\n# function that is doing inorder traversal\ndef fun(root, count, k):\n    if root is None:\n        return\n\n    fun(root.left, count, k)\n    count[0] += 1\n   \tif count[0] == k:\n        ans[0] = root.value\n        return\n    fun(root.right, count, k)\n\ndef main():\n    # creating a tree \n    #     5\n    #    \/ \\\n    #   3   7\n    #  \/ \\   \\\n    # 1   4   9\n    \n    head = Node(5)\n    head.left = Node(3)\n    head.right = Node(7)\n    head.left.left = Node(1)\n    head.left.right = Node(4)\n    head.right.right =  Node(9)\n    \n    # k is 5, so the 5th smallest is value is 7 here \n    # 1 -> 1\n    # 2 -> 3\n    # 3 -> 4\n    # 4 -> 5\n    # 5 -> 7\n    # 6 -> 9\n\n    k = 5\n    count = [0]\n\n    fun(head, count, k)\n    # prints 7\n    print(f"{k}th smallest values is: {ans[0]}")\n\nif __name__ == "__main__":\n    main()<\/pre><\/div>\n\n\n\n
    Output:<\/strong> <\/p>\n\n\n\n
    7<\/code><\/pre>\n\n\n\n
    As we are just iterating the values of the tree so in the worst case time complexity will be O(n). If the element is present at the last. Space complexity will reduced to O(1) as no extra space is required.\u00a0<\/p>\n\n\n\n
    We can compare both the approach to check which one is better:<\/p>\n\n\n\n
    Approach<\/th>Time Complexity<\/strong><\/th>Space Complexity<\/strong><\/th>Description<\/strong><\/th><\/tr><\/thead>
    Brute Force<\/td>O(n Log(n))<\/td>O(n)<\/td>We are sorting the array which requires log(n) time complexity. Also, we are sorting the values in the array which requires O(n) space complexity.<\/td><\/tr>
    Optimized Approach<\/td>O(n)<\/td>O(1)<\/td>We are only traversing the tree once.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
    Conclusion <\/strong><\/h2>\n\n\n\n
    In this article, we learned how to find the kth smallest element of a Binary Search Tree. Some other important problems asked in interviews are how to delete node in BST<\/a>, perform zig-zag traversal<\/a>, and print the top view of a binary tree<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Learn how to find the kth smallest element in the BST using inorder traversal approach with implementation in C++, Java and Python.<\/p>\n","protected":false},"author":14,"featured_media":1669,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1667","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1667","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1667"}],"version-history":[{"count":5,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1667\/revisions"}],"predecessor-version":[{"id":2200,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1667\/revisions\/2200"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1669"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1667"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1667"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1667"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}