[C++] Simple solution No Extra function | Recursion and Iteration | With Explanation |
Intuition\n Describe your first thoughts on how to solve this problem. \nThe inorder traversal of BST always gives us the sorted array of nodes since,\nLeft sub
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe inorder traversal of BST always gives us the sorted array of nodes since,\n**Left subtree nodes < current node < Right subtree nodes.**\n\nPlease find both recursive and iterative approach below and if you face any problem , let me know in comments. Please Do Upvote.\n\n# Approach 1 - Recursion\n<!-- Describe your approach to solving the problem. -->\nWe are using inorder traversal and add one condition such that whenever we get kth element we stop the recursion.\n# Complexity\n- Time complexity: O(h + k), h = Height of bst\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n) (Recursive stack memory)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code 1\nWith Extra Function\n```\nclass Solution {\npublic:\n    int ans;\n    void inorder(TreeNode* root, int& k)\n    {\n        if(!root)   return;\n        inorder(root->left,k);\n        k--;\n        if(k==0){  \n            ans=root->val;\n            return;\n        }\n        inorder(root->right,k);\n    }\n    int kthSmallest(TreeNode* root, int k) {\n        inorder(root, k);\n        return ans;\n    }\n};\n```\n# Code 2\nWithout Extra Function\n```\nclass Solution {\npublic:\n    int ans;\n    int kthSmallest(TreeNode* root, int &k) {\n        if(root){\n            kthSmallest(root->left,k);\n            k--;\n            if(k==0) ans=root->val;\n            kthSmallest(root->right,k);\n        }\n        return ans;\n    }\n};\n```\n# Approach 2 - Iterative\n<!-- Describe your approach to solving the problem. -->\nWe are using inorder traversal stack approach and add one condition such that whenever we get kth element we return that.\n# Complexity\n- Time complexity: O(h + k), h = Height of bst\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n) (Worst Case n = k)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int kthSmallest(TreeNode* root, int k) {\n        stack<TreeNode*> todo;\n        while (root || !todo.empty()) {\n            while (root) {\n                todo.push(root);\n                root = root -> left;\n            }\n            root = todo.top();\n            todo.pop();\n            if(--k == 0) return root->val;\n            root = root -> right;\n        }\n        return 0;\n    }\n};\n```\n\n**Feel free to ask any question in the comment section.\nIf you like this solution, do UPVOTE.**\n
['Stack', 'Depth-First Search', 'Binary Search Tree', 'Recursion', 'C++']