✅🔥 Recursion & Vector Solutions with Complexity Analysis! - C++/Java/Python
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind this solution is to perform an inorder traversal of the binary sea
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind this solution is to perform an inorder traversal of the binary search tree to collect values in ascending order. Once the values are collected, the kth smallest value can be easily retrieved.\n\n# Approach 01\n<!-- Describe your approach to solving the problem. -->\n1. Using ***Vector.***\n1. Perform an inorder traversal, which involves visiting the left subtree, then the root, and finally the right subtree.\n1. Store the values from the left side in a vector, resulting in an increasing order of values.\n1. Return the (k-1)th element from the vector as it corresponds to the kth smallest element in the binary search tree. The vector is in increasing order, making it easy to access the kth smallest element directly.\n\n# Complexity\n- Time complexity: The time complexity of this solution is O(n), where n is the number of nodes in the binary search tree. The inorder traversal visits each node once.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The space complexity is O(n), as the solution uses a list to store the values collected during traversal. In the worst case, when the binary search tree is skewed, the list could contain all node values.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int kthSmallest(TreeNode* root, int k) {\n        vector<int> temp;\n        inorder(root, temp);\n        return temp[k-1];\n    }\n    \n    void inorder(TreeNode* root, vector<int> &temp){\n        if(!root) return;\n        inorder(root->left, temp);\n        temp.push_back(root->val);\n        inorder(root->right, temp);\n    }\n};\n```\n```Java []\nclass Solution {\n    List<Integer> values = new ArrayList<>();\n\n    public int kthSmallest(TreeNode root, int k) {\n        inorder(root);\n        return values.get(k - 1);\n    }\n\n    private void inorder(TreeNode root) {\n        if (root == null) {\n            return;\n        }\n        inorder(root.left);\n        values.add(root.val);\n        inorder(root.right);\n    }\n}\n```\n```python []\nclass Solution(object):\n    def kthSmallest(self, root, k):\n        values = []\n        self.inorder(root, values)\n        return values[k - 1]\n\n    def inorder(self, root, values):\n        if root is None:\n            return\n        self.inorder(root.left, values)\n        values.append(root.val)\n        self.inorder(root.right, values)\n```\n\n---\n# Approach 02\n<!-- Describe your approach to solving the problem. -->\n1. Using ***Recursion.*** \n1. Perform an in-order traversal of the binary search tree.\n1. In each recursive call, check if the kth smallest element has been found.\n1. If found, update the result and stop further traversal.\n1. Return the result after the traversal.\n\n# Complexity\n- Time complexity: The time complexity of this solution is O(n), where n is the number of nodes in the binary search tree. The inorder traversal visits each node once.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The space complexity is O(h), where h is the height of the binary search tree. The space complexity is determined by the recursion stack.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int ans;\n    \n    int kthSmallest(TreeNode* root, int k) {\n        inorder(root, k);\n        return ans;\n    }\n    \n    void inorder(TreeNode* root, int& k) {\n        if (!root) return;\n        inorder(root->left, k);\n        if (--k == 0){\n            ans = root->val;\n            return;\n        } \n        inorder(root->right, k);\n    }  \n};\n```\n```Java []\nclass Solution {\n    private int count = 0;\n    private int result = 0;\n\n    public int kthSmallest(TreeNode root, int k) {\n        inorderTraversal(root, k);\n        return result;\n    }\n\n    private void inorderTraversal(TreeNode node, int k) {\n        if (node == null || count >= k) {\n            return;\n        }\n\n        inorderTraversal(node.left, k);\n\n        count++;\n        if (count == k) {\n            result = node.val;\n            return;\n        }\n\n        inorderTraversal(node.right, k);\n    }\n}\n```\n```python []\nclass Solution(object):\n    def kthSmallest(self, root, k):\n        self.count = 0\n        self.result = 0\n        self.inorderTraversal(root, k)\n        return self.result\n    \n    def inorderTraversal(self, node, k):\n        if not node or self.count >= k:\n            return\n        \n        self.inorderTraversal(node.left, k)\n        \n        self.count += 1\n        if self.count == k:\n            self.result = node.val\n            return\n        \n        self.inorderTraversal(node.right, k)\n```\n\n---\n\n\n> **Please upvote this solution**\n>
['Depth-First Search', 'Binary Search Tree', 'Recursion', 'Python', 'C++', 'Java', 'Python3']