Recursive approach✅ | O( n)✅ | (Step by step explanation)✅
Intuition\nThe problem asks for finding the kth smallest element in a binary search tree (BST). A binary search tree is a binary tree where, for each node, the 
# Intuition\nThe problem asks for finding the kth smallest element in a binary search tree (BST). A binary search tree is a binary tree where, for each node, the values of all nodes in its left subtree are less than the node\'s value, and the values of all nodes in its right subtree are greater than the node\'s value.\n\n# Approach\nThe approach involves performing an in-order traversal of the BST, which visits the nodes in ascending order. By collecting the values of the nodes during the traversal, we can create an array representing the sorted order of elements in the BST. The kth smallest element will be at index k-1 in this array.\n\n1. **In-order Traversal**: Traverse the BST in in-order fashion.\n\n   **Reason**: In-order traversal ensures that we visit the nodes in ascending order.\n\n2. **Collect Values**: During the traversal, collect the values of the nodes in a vector.\n\n   **Reason**: We need to create an array representing the sorted order of elements.\n\n3. **Result**: Return the element at index k-1 in the vector.\n\n   **Reason**: The kth smallest element will be at index k-1 in the sorted order.\n\n# Complexity\n- **Time complexity**: O(n)\n  - We perform in-order traversal, visiting each node once.\n- **Space complexity**: O(n)\n  - The space required to store the values in the vector during traversal.\n\n# Code\n\n\n<details open>\n  <summary>Python Solution</summary>\n\n```python\nclass Solution:\n    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n        arr = []\n\n        def inOrder(root ):\n            if root == None:\n                return \n\n            inOrder(root.left ) \n            arr.append(root.val)\n            inOrder(root.right)\n\n\n        inOrder(root)\n        \n        return arr[k-1]\n```\n</details>\n\n<details open>\n  <summary>C++ Solution</summary>\n\n```cpp\nclass Solution {\npublic:\n    int kthSmallest(TreeNode* root, int k) {\n        vector<int> arr;\n        inOrder(root , arr);\n\n        return arr[k - 1];\n    }\n\nprivate:\n    void inOrder(TreeNode* root, vector<int> &arr) {\n        if (root == NULL) {\n            return;\n        }\n\n        inOrder(root->left , arr);\n        arr.push_back(root->val);\n        inOrder(root->right , arr);\n        \n    }\n};\n```\n</details>\n\n# Please upvote the solution if you understood it.\n![1_3vhNKl1AW3wdbkTshO9ryQ.jpg](https://assets.leetcode.com/users/images/0161dd3b-ad9f-4cf6-8c43-49c2e670cc21_1699210823.334661.jpeg)\n
['Tree', 'Depth-First Search', 'Binary Search Tree', 'Recursion', 'C++', 'Python3']