🔥☠️💀5 Different ways in C++/Python3 🐍/Java/C/Python 🔥☠️💀 Explained with images✅✅ beats 💯
Intuition\n\n\n\n\nC++ []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n 
# Intuition\n![0ehh83fsnh811.jpg](https://assets.leetcode.com/users/images/ee50cada-fd59-496c-9f80-87d093a32d95_1712713818.055228.jpeg)\n![Screenshot 2024-04-10 071934.png](https://assets.leetcode.com/users/images/0a00c2d0-1255-4f03-8379-1462b8520f2a_1712713824.7129164.png)\n![Screenshot 2024-04-11 150226.png](https://assets.leetcode.com/users/images/16b11070-c855-4c03-acc8-9efed4087871_1712828031.1637602.png)\n\n```C++ []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),\n * right(right) {}\n * };\n */\nclass Solution {\n    vector<int> res;\n    void inorder(TreeNode* root, vector<int>& res) {\n        if (root) {\n            inorder(root->left, res);\n            res.push_back(root->val);\n            inorder(root->right, res);\n        }\n        return;\n    }\n\npublic:\n    int kthSmallest(TreeNode* root, int k) {\n        inorder(root, res);\n        return res[k - 1];\n    }\n};\n```\n```python3 []\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n        res = []\n\n        def _inorder(node):\n            if not node:\n                return\n            _inorder(node.left)\n            if len(res) == k:\n                return\n            res.append(node.val)\n            _inorder(node.right)\n\n        _inorder(root)\n        return res[-1]\n```\n```C []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     struct TreeNode *left;\n *     struct TreeNode *right;\n * };\n */\nvoid search(struct TreeNode* root, int* arr, int* idx) {\n    if (!root)\n        return;\n    search(root->left, arr, idx);\n    arr[(*idx)++] = root->val;\n    search(root->right, arr, idx);\n    return;\n}\n\nint kthSmallest(struct TreeNode* root, int k) {\n    int* arr = (int*)malloc(10000 * sizeof(int));\n    int idx = 0;\n    search(root, arr, &idx);\n    int ans = arr[k - 1];\n    free(arr);\n    return ans;\n}\n```\n```Java []\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n * int val;\n * TreeNode left;\n * TreeNode right;\n * TreeNode() {}\n * TreeNode(int val) { this.val = val; }\n * TreeNode(int val, TreeNode left, TreeNode right) {\n * this.val = val;\n * this.left = left;\n * this.right = right;\n * }\n * }\n */\nclass Solution {\n    ArrayList<Integer> res = new ArrayList<>();\n\n    private void inorder(TreeNode root, int k) {\n        if (root == null)\n            return;\n        inorder(root.left, k);\n        res.add(root.val);\n        if (res.size() == k)\n            return;\n        inorder(root.right, k);\n        return;\n    }\n\n    public int kthSmallest(TreeNode root, int k) {\n        inorder(root, k);\n        return res.get(k - 1);\n    }\n}\n```\n```python []\n# Definition for a binary tree node.\n# class TreeNode(object):\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution(object):\n    def kthSmallest(self, root, k):\n        """\n        :type root: TreeNode\n        :type k: int\n        :rtype: int\n        """\n        curr = root\n        cnt  = 0\n        ans  = 0\n        while curr:\n\n            if not curr.left:\n                cnt += 1\n                if cnt == k:\n                    return curr.val\n                \n                curr = curr.right\n            \n            else:\n                prev = curr.left\n                while prev.right and prev.right.val != curr.val:\n                    prev = prev.right\n\n                if not prev.right:\n                    prev.right = curr\n                    curr = curr.left\n                else:\n                    prev.right = None\n                    cnt += 1\n                    if cnt == k:\n                        return curr.val\n                \n                    curr = curr.right\n        return ans\n```\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(n)\n# Code\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),\n * right(right) {}\n * };\n */\nclass Solution {\n    vector<int> res;\n    void inorder(TreeNode* root, vector<int>& res) {\n        if (root) {\n            inorder(root->left, res);\n            res.push_back(root->val);\n            inorder(root->right, res);\n        }\n        return;\n    }\n\npublic:\n    int kthSmallest(TreeNode* root, int k) {\n        inorder(root, res);\n        return res[k - 1];\n    }\n};\n```\n# Please Upvote if it\'s useful for you please..\n![th.jpeg](https://assets.leetcode.com/users/images/b77b4adb-eda1-4e12-9e1f-032a97c6d069_1712713942.4053571.jpeg)\n
['Tree', 'Depth-First Search', 'Binary Search Tree', 'C', 'Binary Tree', 'Python', 'C++', 'Java', 'Python3', 'C#']