I bet you will understand | Brute->Better->Optimal | Beginner Friendly | C++
(1) Naive Approach: \n## Intuition:\nWe can do traversal of the given tree using any traversal technique and store the node values in an array/vector. Then we c
# (1) Naive Approach: \n## Intuition:\nWe can do traversal of the given tree using any traversal technique and store the node values in an array/vector. Then we can sort the array in ascending order such that the 1st smallest element comes at 0th index, 2nd smallest element at 1st index ... kth samllest element at k-1th index.\n\n## Algorithm:\n1. Initialize an empty vector \'v\'.\n2. Do any traversal (lets say preorder) and store the node values in v.\n3. Sort vector v in ascending order.\n4. Return v[k-1].\n\n## Complexity:\n- Time complexity: $$O(n)$$ + $$O(nlogn)$$ -> $$O(nlogn)$$\n  O(n) for traversing the Tree and O(nlogn) for sorting the vector of size n.\n\n- Space complexity:$$O(n)$$ + recursive stack space \n\n## Code\n```\nclass Solution {\npublic:\n    void preOrderTraversal(TreeNode* root, vector<int> &v){\n        if(root == NULL)    return;\n        \n        //root, left, right \n        v.push_back(root->val);\n        preOrderTraversal(root->left, v);\n        preOrderTraversal(root->right, v);      \n    }\n    int kthSmallest(TreeNode* root, int k) {\n        vector<int> v; \n        preOrderTraversal(root, v);\n        sort(v.begin(), v.end());\n        return v[k-1];\n    }\n};\n```\n\n# (2) Better Approach: \n## Why Better? \nIn the above approach we are using an extra O(nlogn) for sorting the vector. We need to remove it somehow so that our time complexity boils down to O(n).\n\nThe naive approach of O(nlogn) can also be converted to O(nlogk) using priority queue as we do in the following array question.\nhttps://leetcode.com/problems/kth-largest-element-in-an-array/\n\nBut, here I will be discussing only the O(n) one. \n\n## Intuition:\nWe know that the tree given to us is a Binary Search Tree, therefore, all the nodes at the left subtree of a given node will be less than the current node value and it will be less then all the nodes at the right subtree of that node.\ni.e.\n\n               N\n              / \\\n             L   R\n        \n             L<N<R in case of BST\n\nSo, we can take advantage of this and do an INORDER TRAVERSAL. The inorder traversal will always result in a sorted array and the extra NlogN that we were using for sorting will be omitted. \n\n## Algorithm\n1. Initialize an empty vector \'v\'.\n2. Do an Inorder traversal and store the node values in v.\n3. Return v[k-1].\n\n## Complexity\n- Time complexity: $$O(n)$$\n  O(n) for traversing the Tree consisting of n nodes.\n- Space complexity:$$O(n)$$ + recursive stack space \n\n## Code\n```\nclass Solution {\npublic:\n    void inOrderTraversal(TreeNode* root, vector<int> &v){\n        if(root == NULL)    return;\n        \n        //left, root, right \n        inOrderTraversal(root->left, v);\n        v.push_back(root->val);\n        inOrderTraversal(root->right, v);      \n    }\n    int kthSmallest(TreeNode* root, int k) {\n        vector<int> v; \n        inOrderTraversal(root, v);\n        return v[k-1];\n    }\n};\n```\n\n# (3) Optimal Approach: O(N) time and O(1) space:\n\nApproach 2 is fine, but there we are still creating an extra vector to store the node values. We can avoid it so that our space complexity further boils down to O(1).\n\n## Intuition:\nWe need the kth smallest element. And, we know that our inorder traversal will first give the 1st smallest element, then 2nd smallest element ... and so on. \nSo, instead of storing the node values inside a vector, we can maintain a \'cnt\' variable to keep track if we have reached kth smallest value or not in the inorder traversal. And then, we can return the value once cnt reaches k value.\n\n## Algorithm:\n1. Initialize a variable, cnt = 0;\n2. Do an Inorder traversal and instead of saving node->val in vector do a cnt++, denoting that we have encountered cnt th smallest element.\n3. Return node->val once cnt == k.\n\n## Complexity:\n- Time complexity: $$O(n)$$\n  O(n) for traversing the Tree consisting of n nodes.\n- Space complexity:$$O(1)$$ + recursive stack space \n\n## Code:\n```\nclass Solution {\npublic:\n    void solve(TreeNode* root, int &cnt, int &ans, int k){\n        if(root == NULL)    return;\n        //left, root, right \n        solve(root->left, cnt, ans, k);\n        cnt++;\n        if(cnt == k){\n            ans = root->val;\n            return;\n        }\n        solve(root->right, cnt, ans, k);\n    }\n    int kthSmallest(TreeNode* root, int k) {\n        \n        int cnt = 0;        \n        int ans;\n        solve(root, cnt, ans, k);\n        return ans;\n    }\n};\n```\n\n# Please upvote the solution if you understood it.\n\n![NRRa.gif](https://assets.leetcode.com/users/images/ac16397a-5dda-46bb-8508-a6caf66f016b_1679243081.1794233.gif)
['Depth-First Search', 'Binary Search Tree', 'Recursion', 'Heap (Priority Queue)', 'C++']