✅ Clean & Easy C++ | Both Iterative and Recursive Methods
Recursive Approach:\n A recursive In-Order Traversal could be performed, and a count value could be maintained to reach to the kth Smallest Node. Below is the i
### Recursive Approach:\n* A recursive `In-Order Traversal` could be performed, and a `count` value could be maintained to reach to the kth Smallest Node. Below is the implementation, which is self explainatory.\n* Time Complexity: **O(N)**, since we are essentially performing a DFS starting at the `root`.\n* Space Complexity: Recursion uses the stack space internally, hence **O(N)**. No additional data structures used to preserve values. Hence, **O(1) auxillary.**\n```c++\nclass Solution {\n    int answer;\npublic:\n    Solution():answer(0){}\n    void Solve(TreeNode *root, int k, int &count){\n        if(not root) \n\t\t  return;\n        Solve(root->left, k, count);\n        count++;\n        if(count==k){\n          answer = root->val;\n          return;\n        }\n        Solve(root->right, k, count);\n    }\n    int kthSmallest(TreeNode* root, int k) {\n        int count = 0;\n        Solve(root,k,count);\n        return answer;\n    }\n};\n```\n\n---\n### Iterative Approach:\n* We could utilize the stack data structure to perform the same traversal and maintain the count value, to reach to the kth smallest Node. Idea is essentially the same as above, instead of using `recursion`, we could use `stack` to write an iterative solution\n* Time Complexity: **O(N)**\n* Space Complexity: **O(N) auxillary space**, since we have used a `stack` data structure.\n* Below is the clean iterative solution.\n```c++\n int kthSmallest(TreeNode* root, int k) {\n        stack<TreeNode*> St;\n        int count = 0;\n        TreeNode *node = root;\n        while(not St.empty() || node){\n            if(node){\n                St.push(node);\n                node = node->left;\n            }else{\n                node = St.top(); St.pop();\n                if(++count==k) return node->val;\n                node = node->right;\n            }\n        }\n        return INT_MIN;\n    }\n```\n\n> Please feel free to comment below your ideas, or any doubt regarding the aforementioned code. :)
['C', 'Iterator']