✅ 🔥 0 ms Runtime Beats 100% User🔥||  Code Idea ✅ ||  Algorithm & Solving Step  ✅ ||
![Screenshot 2024-12-10 at 4.53.58\u202FPM.png](https://assets.leetcode.com/users/images/a78936c7-b0c1-49ee-b7fa-49d8345a42c9_1733829971.7884712.png)\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n\n### **Intuition** :\n1. A **Binary Search Tree** (BST) is structured such that:\n   - The left subtree contains values smaller than the root.\n   - The right subtree contains values larger than the root.\n2. An **inorder traversal** of a BST yields values in sorted order. This makes it straightforward to extract the \\( k \\)-th smallest value by counting nodes as we traverse the tree.\n\n---\n\n### **Approaches** :\n\n#### **1. Simple Inorder Traversal (Recursive or Iterative)**\nPerform a full inorder traversal and stop as soon as the \\( k \\)-th smallest element is reached.\n\n#### **2. Follow-Up Optimization (Dynamic BST Modifications)**\nIf the BST is frequently modified (insertions or deletions), augment the tree nodes to include the **size of the subtree rooted at each node**. This allows us to perform an \\( O(\\log n) \\)-time search for the \\( k \\)-th smallest element without a full traversal.\n\n---\n\n### **Algorithm** :\n\n#### **Simple Inorder Traversal**\n1. Define a counter to track the number of visited nodes.\n2. Perform an inorder traversal:\n   - Recurse into the left subtree.\n   - Visit the current node (increment the counter).\n   - If the counter matches \\( k \\), return the current node\'s value.\n   - Recurse into the right subtree.\n\n---\n\n### **Steps in Code** :\n\n#### Python Implementation :\n```python\nclass Solution:\n    def kthSmallest(self, root: TreeNode, k: int) -> int:\n        def inorder(node):\n            if not node:\n                return\n            # Traverse left subtree\n            yield from inorder(node.left)\n            # Visit current node\n            yield node.val\n            # Traverse right subtree\n            yield from inorder(node.right)\n\n        # Iterate through inorder traversal and find the k-th smallest\n        gen = inorder(root)\n        for _ in range(k):\n            result = next(gen)\n        return result\n```\n\n---\n\n#### C++ Implementation :\n```cpp\n#include <stack>\nusing namespace std;\nclass Solution {\npublic:\n    int kthSmallest(TreeNode* root, int k) {\n        stack<TreeNode*> st;\n        TreeNode* current = root;\n        int count = 0;\n\n        while (!st.empty() || current) {\n            while (current) {\n                st.push(current);\n                current = current->left;\n            }\n\n            current = st.top();\n            st.pop();\n            count++;\n            if (count == k) return current->val;\n            current = current->right;\n        }\n\n        return -1; // This line should never be reached\n    }\n};\n```\n\n---\n\n#### Java Implementation :\n```java\nimport java.util.Stack;\nclass Solution {\n    public int kthSmallest(TreeNode root, int k) {\n        Stack<TreeNode> stack = new Stack<>();\n        TreeNode current = root;\n        int count = 0;\n\n        while (!stack.isEmpty() || current != null) {\n            while (current != null) {\n                stack.push(current);\n                current = current.left;\n            }\n\n            current = stack.pop();\n            count++;\n            if (count == k) return current.val;\n            current = current.right;\n        }\n\n        return -1; // This line should never be reached\n    }\n}\n```\n\n---\n\n### **Complexity** :\n\n#### Time Complexity:\n- **Inorder Traversal**:\n  -  O(n)  for a full traversal.\n  -  O(k)  if we stop as soon as the  k -th element is found.\n- **Augmented Tree (Follow-Up)**:\n  -  O(log n)  for each query if subtree sizes are maintained.\n\n#### Space Complexity:\n- O(h) , where  h  is the height of the tree (due to the recursive call stack or iterative stack).\n\n---\n\n### **Another Aproach  C++ Solution** :\n\n```cpp\n#include <stack>\nusing namespace std;\n\nstruct TreeNode {\n    int val;\n    TreeNode *left;\n    TreeNode *right;\n    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n};\n\nclass Solution {\npublic:\n    int kthSmallest(TreeNode* root, int k) {\n        stack<TreeNode*> st;\n        TreeNode* current = root;\n        int count = 0;\n\n        // Iterative inorder traversal\n        while (!st.empty() || current) {\n            // Go to the leftmost node\n            while (current) {\n                st.push(current);\n                current = current->left;\n            }\n\n            // Visit the node at the top of the stack\n            current = st.top();\n            st.pop();\n            count++;\n\n            // If this is the k-th smallest, return its value\n            if (count == k) {\n                return current->val;\n            }\n\n            // Move to the right subtree\n            current = current->right;\n        }\n\n        return -1; // This line should never be reached if k is valid\n    }\n};\n```\n\n---\n\n### **Explanation** :\n\n1. **Inorder Traversal**:\n   - Traverse the tree iteratively using a stack.\n   - Push all left children onto the stack until reaching a `nullptr`.\n   - Pop the stack to process the node, increment the counter, and check if it matches \\( k \\).\n   - Move to the right child and repeat.\n\n2. **Key Observations**:\n   - The stack-based traversal ensures we process nodes in ascending order for BSTs.\n   - The counter tracks the number of processed nodes.\n\n3. **Edge Cases**:\n   - \\( k = 1 \\): Return the smallest element.\n   - \\( k = n \\): Return the largest element.\n\n---\n\n### **Complexity** :\n\n#### Time Complexity:\n- **Traversal**:  O(k)  for the  k -th smallest element (we stop after processing \\( k \\) nodes).\n\n#### Space Complexity:\n- **Stack Size**:  O(h) , where  h  is the height of the tree. In the worst case,  h = O(n) for a skewed tree and  h = O(log n)  for a balanced tree.\n\n---\n\n### **Example Walkthrough** :\n\n#### Input:\n```plaintext\nroot = [3,1,4,null,2], k = 1\n```\n\nTree structure:\n```\n    3\n   / \\\n  1   4\n   \\\n    2\n```\n\n#### Execution:\n1. Stack: Push `3 -> 1`.\n2. Visit `1` (increment count to 1).\n3. \\( k = 1 \\): Return `1`.\n\n#### Output:\n```plaintext\n1\n```\n---\n
['Tree', 'Depth-First Search', 'Binary Search Tree', 'Binary Tree', 'C++', 'Java', 'Python3']