[Java/Python] Using Stack as Iterator - Picture explain - Clean code - O(H + k)
\u2714\uFE0F Solution 1: Inorder Traversal\n- We traverse inorder in BST (Left - Root - Right) then we have sortedArr as non-decreasing sorted array af elements
**\u2714\uFE0F Solution 1: Inorder Traversal**\n- We traverse inorder in BST (Left - Root - Right) then we have `sortedArr` as non-decreasing sorted array af elements in BST. \n- The result is the `kth` element in our `sortedArr`.\n```java\nclass Solution {\n    List<Integer> sortedArr = new ArrayList<>();\n    public int kthSmallest(TreeNode root, int k) {\n        inorderTraverse(root);\n        return sortedArr.get(k-1);\n    }\n    void inorderTraverse(TreeNode root) {\n        if (root == null) return;\n        inorderTraverse(root.left);\n        sortedArr.add(root.val);\n        inorderTraverse(root.right);\n    }\n}\n```\n**Complexity**\n- Time: `O(N)`\n- Space: `O(N)`\n\n---\n**\u2714\uFE0F Solution 2: Using Stack as Iterator**\n- We use idea from [173. Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/discuss/965584) to iterate elements in order in O(H) in Space Comlpexity.\n- The idea is that we iterate through the BST, we pop from smallest elements and we just need to pop `k` times to get the `k_th` smallest element.\n![image](https://assets.leetcode.com/users/hiepit/image_1589996326.png)\n\n<iframe src="https://leetcode.com/playground/PoiZ2FKw/shared" frameBorder="0" width="100%" height="400"></iframe>\n\n**Complexity**\n- Time: `O(H + k)`, where `H` is the height of the BST.\n- Space: `O(H)`\n\n\nPlease help to **UPVOTE** if this post is useful for you. \nIf you have any questions, feel free to comment below.\nHappy coding!\n\n
['Stack', 'Depth-First Search']