C++ Easy Solution without Recursion using Inorder Traversal
Intuition\nThe code implements an iterative INORDER TRAVERSAL on a BST using a stack. In inorder traversal, nodes are visited in a left-root-right sequence, ens
# Intuition\nThe code implements an iterative **INORDER TRAVERSA**L on a BST using a stack. In inorder traversal, nodes are visited in a left-root-right sequence, ensuring they\'re processed in ascending order due to the BST property. The algorithm starts from the root, pushes nodes to the stack while moving left, and processes them when no left child exists. It counts nodes until it reaches the kth smallest, efficiently leveraging the BST\'s sorted order for quick retrieval.\n\n# Approach\n1. **Stack Initialization and Traversal Setup :** \n- Initialize an empty stack s to simulate the recursive call stack used in inorder traversal.\n- Start with node set to the root of the BST for traversal.\n\n2. **Iterative Inorder Traversal :**\n- Use a while loop to continue traversal until the stack is empty and node is null (no more nodes to process).\n- **Inside the loop :**\na) If node is not null, push it onto the stack (s.push(node)) and move to its left child (node = node->left). This effectively moves to the leftmost node of the current subtree.\nb) If node is null (no left child to explore), pop the top node (temp = s.top()) from the stack to process it.\n\n3. **Processing Nodes :**\n- Check if the current node (temp) is the kth smallest (if (i == k)). If true, return its value (temp->val).\n- Update a temporary variable x with the current node\'s value (x = temp->val). This helps in tracking the last visited node\'s value.\n- Increment the counter i to track the number of nodes visited.\n\n4. **Move to Right Subtree :** Move to the right child of the current node (node = temp->right). This step prepares to process the right subtree of the current node in subsequent iterations.\n\n5. **Completion and Result :**\n- The loop continues until either finding the kth smallest node or exhausting all nodes in the BST.\n- If the loop exits without finding the kth smallest (i < k), return -1, indicating the kth smallest value doesn\'t exist (though it typically should in a valid BST).\n\n\n# Inorder Traversal Advantage:\n\nThe use of inorder traversal ensures that nodes are visited in ascending order of their values due to the BST property. This property allows for efficient determination of the kth smallest node without needing to examine every node, making the algorithm efficient with a Time Complexity of O(N) and Space Complexity of O(H), where H is the height of the tree.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(H) [ where H is the Height of the Tree ]\n\n# Code\n```\nclass Solution {\npublic:\n    int kthSmallest(TreeNode* root, int k) {\n        stack<TreeNode*> s;\n        TreeNode* node=root;\n\n        int i=1;\n        long long int x=LLONG_MAX;\n\n        while(s.size()>0 or node){\n            if(node){\n                s.push(node);\n                node=node->left;\n            }\n\n            else{\n                TreeNode* temp=s.top();\n                s.pop();\n                if(i==k) return temp->val;\n                if(x!=LLONG_MAX){\n                    x=temp->val;\n                }\n                i++;\n                node=temp->right;\n            }\n            \n        }\n        return -1;\n    }\n};\n```
['Stack', 'Depth-First Search', 'C++']