AlgoExplained.dev

def kthSmallest(root, k):
Defines the main function that takes the root of a BST and an integer k, returning the kth smallest value (1-indexed) in the tree using iterative inorder traversal.
    stack = []
Initialize an empty stack to simulate the recursive call stack. The stack will hold the path of nodes from the root down to the current position, enabling us to backtrack after processing left subtrees.
    curr = root
Pointer to track the current node being explored. We start at the root and will navigate left, right, and up using the stack.
    while stack or curr:
Main loop: continue as long as there are nodes to process on the stack or unexplored nodes remaining. Both conditions are needed — `stack` handles backtracking, `curr` handles moving into new subtrees.
        while curr:
Inner loop: traverse as far left as possible. In a BST, the leftmost node is the smallest, so we push all left-path nodes onto the stack to process them in ascending order.
            stack.append(curr)
Push the current node onto the stack before going to its left child. This ensures we can return to this node after processing its entire left subtree.
            curr = curr.left
Move to the left child. This continues until we reach the leftmost node (curr becomes None), at which point the stack's top element is the next smallest unvisited node.
        curr = stack.pop()
Pop the top node — this is the next node in sorted order. Since all smaller nodes (left subtree) have already been processed, this is the correct next element in the inorder sequence.
        k -= 1
Decrement the counter. We have visited one more node in sorted order. When k reaches 0, the current node is the kth smallest.
        if k == 0:
Check if we have found the kth smallest element. This enables early termination — we stop as soon as the answer is found without traversing the rest of the tree.
            return curr.val
Return the value of the kth smallest node. This is the final answer to the problem.
        curr = curr.right
Move to the right child to continue the inorder traversal. The right subtree contains all values larger than the current node. If there is no right child, the loop continues by popping the next node from the stack.

public int kthSmallest(TreeNode root, int k) {
Public entry point that takes the root of a BST and integer k, returning the kth smallest value using iterative inorder traversal with an explicit stack.
    Stack<TreeNode> stack = new Stack<>();
Initialize a stack to hold TreeNode references. This simulates the recursion call stack for inorder traversal, keeping track of the path back up the tree.
    TreeNode curr = root;
Pointer to track the current node. Starts at the root and navigates left, right, and back through the stack.
    while (curr != null || !stack.isEmpty()) {
Main loop continues while there are unvisited nodes. `curr != null` means there are new nodes to explore; `!stack.isEmpty()` means there are nodes to backtrack to.
        while (curr != null) {
Inner loop: push all left children onto the stack to reach the leftmost (smallest) node. This is the first phase of inorder traversal.
            stack.push(curr);
Push the current node onto the stack before descending to its left child, so we can return to process it after the left subtree is done.
            curr = curr.left;
Move to the left child. Loop continues until curr is null, meaning we've reached the bottom-left of the current subtree.
        curr = stack.pop();
Pop the top node — the next node in inorder (ascending) order. Its entire left subtree has already been processed.
        if (--k == 0) return curr.val;
Pre-decrement k and check if it's zero. If so, the current node is the kth smallest — return its value immediately. The `--k` inline saves a line while decrementing before the comparison.
        curr = curr.right;
Move to the right child. All remaining values in the right subtree are larger than the current node. If curr is null, the outer loop continues by popping from the stack.
    }
End of the main while loop. In practice, the return inside the loop always executes since k is guaranteed to be valid (1 <= k <= n).
    return -1;
Fallback return (never reached given valid input). Required by Java's compiler since the method must return an int on all paths.
}
End of the kthSmallest method.

class Solution {
Defines the Solution class for LeetCode. Contains a single public method that finds the kth smallest element using iterative inorder traversal.
public:
Public access specifier for the LeetCode-required entry point method.
    int kthSmallest(TreeNode* root, int k) {
Entry point taking a BST root pointer and integer k. Returns the kth smallest value using iterative inorder traversal with an explicit stack.
        stack<TreeNode*> st;
Initialize a stack of TreeNode pointers. This simulates the recursion stack for inorder traversal, storing the path back to parent nodes.
        TreeNode* curr = root;
Pointer to the current node being explored, starting at the root.
        while (curr || !st.empty()) {
Main loop: continue while there are nodes to explore (`curr`) or nodes on the stack to backtrack to (`!st.empty()`). Both conditions ensure complete traversal.
            while (curr) {
Inner loop: go as far left as possible, pushing each node onto the stack. This reaches the leftmost (smallest) node in the current subtree.
                st.push(curr);
Push the current node onto the stack before descending left. This allows us to return to this node after processing its left subtree.
                curr = curr->left;
Move to the left child. The loop exits when curr is null, meaning we've reached the bottom-left of the current path.
            curr = st.top(); st.pop();
Retrieve and remove the top node from the stack — this is the next node in sorted (ascending) order. Combined into one line since both operations always happen together.
            if (--k == 0) return curr->val;
Pre-decrement k. If k reaches zero, the current node is the kth smallest — return its value immediately. This enables early termination without visiting the rest of the tree.
            curr = curr->right;
Move to the right child to continue inorder traversal. The right subtree contains all values greater than the current node. If curr is null, the outer loop pops the next ancestor.
        }
End of the main while loop. The return inside the loop always executes for valid k.
        return -1;
Fallback return (unreachable with valid input). Required because the compiler must see a return statement on all code paths.
    }
End of the kthSmallest method.
};
End of the Solution class.