56.1 (Approach 1: Iterative) | O(n)✅ | Python & C++(Step by step explanation)✅
Intuition\nThe problem asks to find the kth smallest element in a binary search tree (BST). Since the left subtree of a node in a BST contains values smaller th
# Intuition\nThe problem asks to find the kth smallest element in a binary search tree (BST). Since the left subtree of a node in a BST contains values smaller than the node\'s value and the right subtree contains values larger than the node\'s value, we can perform an in-order traversal of the BST to get the elements in sorted order. By traversing the BST in-order, we can efficiently find the kth smallest element.\n\n# Approach:\n\nTo find the kth smallest element in a binary search tree (BST), we utilize an in-order traversal approach. In a BST, an in-order traversal visits nodes in ascending order of their values. Therefore, by performing an in-order traversal and keeping track of the count of visited nodes, we can efficiently find the kth smallest element.\n\n1. **Initialization:** We initialize an empty stack to help us perform the in-order traversal. We also initialize a variable `n` to keep track of the count of visited nodes.\n\n2. **In-Order Traversal:**\n   - We start the traversal from the root node of the BST.\n   - While the current node `temp` is not None or the stack is not empty:\n     - We traverse as far left as possible by pushing each node encountered onto the stack.\n     - Once we reach the leftmost node (i.e., when `temp` becomes None), we start popping nodes from the stack one by one.\n     - For each popped node:\n       - We increment the count `n` to keep track of the number of visited nodes.\n       - If `n` becomes equal to k, we return the value of the current node as it represents the kth smallest element.\n       - If `n` is less than k, we move to the right subtree of the current node and continue the traversal.\n\n3. **Result:** After completing the traversal, we return the value of the kth smallest element found during the traversal.\n\n# Example\nSuppose we have the following binary search tree (BST):\n\n```\n        5\n       / \\\n      3   6\n     / \\   \\\n    2   4   7\n```\n\nLet\'s find the 3rd smallest element in this BST using the described approach:\n\n1. **Initialization:** We start with an empty stack and `n = 0`.\n\n2. **In-Order Traversal:**\n   - We start from the root node (5) and traverse as far left as possible, pushing nodes onto the stack: `[5, 3, 2]`.\n   - We pop the leftmost node (2) from the stack, increment `n` to 1.\n   - We pop the next node (3) from the stack, increment `n` to 2.\n   - As `n` is not equal to k (3), we move to the right subtree of node 3.\n   - We traverse as far left as possible in the right subtree of node 3, pushing nodes onto the stack: `[5, 4]`.\n   - We pop the leftmost node (4) from the stack, increment `n` to 3.\n   - Now, `n` is equal to k (3), so we return the value of the current node (4), which is the 3rd smallest element.\n\n3. **Result:** The 3rd smallest element in the BST is 4.\n\n**Complexity:**\n- **Time Complexity:** The time complexity of this approach is O(H + k), where H is the height of the BST. In the worst-case scenario, we may need to traverse the entire height of the tree to find the kth smallest element. Additionally, we need to pop k elements from the stack.\n- **Space Complexity:** The space complexity is O(H) for the stack, where H is the height of the tree. In the worst case, the stack may contain all nodes of the longest path from the root to the leaf node.\n\n# Code(Python)\n```python\nclass Solution:\n    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n        # Initialize an empty stack to perform in-order traversal\n        stack = []\n        # Initialize a variable to count the number of visited nodes\n        n = 0\n        # Start with the root node\n        temp = root\n\n        # Perform in-order traversal\n        while temp or stack:\n            # Traverse as far left as possible, pushing each node onto the stack\n            while temp:\n                stack.append(temp)\n                temp = temp.left\n            # Once we reach the leftmost node, start popping nodes from the stack\n            temp = stack.pop()\n            # Increment the count of visited nodes\n            n += 1\n            # If count becomes equal to k, return the value of the current node\n            if n == k:\n                return temp.val\n            # Move to the right subtree and continue traversal\n            temp = temp.right\n\n        # Return 0 if kth smallest element not found (shouldn\'t happen in a valid BST)\n        return 0\n```\n\n# Code(C++)\n```c++\nclass Solution {\npublic:\n    int kthSmallest(TreeNode* root, int k) {\n        // Initialize a stack to perform in-order traversal\n        stack<TreeNode*> stack;\n        // Initialize a variable to count the number of visited nodes\n        int n = 0;\n        // Start with the root node\n        TreeNode* temp = root;\n\n        // Perform in-order traversal\n        while (temp || !stack.empty()) {\n            // Traverse as far left as possible, pushing each node onto the stack\n            while (temp) {\n                stack.push(temp);\n                temp = temp->left;\n            }\n            // Once we reach the leftmost node, start popping nodes from the stack\n            temp = stack.top();\n            stack.pop();\n            // Increment the count of visited nodes\n            n += 1;\n            // If count becomes equal to k, return the value of the current node\n            if (n == k) {\n                return temp->val;\n            }\n            // Move to the right subtree and continue traversal\n            temp = temp->right;\n        }\n\n        // Return 0 if kth smallest element not found (shouldn\'t happen in a valid BST)\n        return 0;\n    }\n};\n```\n\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\n
['Tree', 'Depth-First Search', 'Binary Search Tree', 'Binary Tree', 'C++', 'Python3']