Kth Smallest Element in a BST – Inorder Traversal Explained (LC 230)

🔍 Problem Overview

The task is to find the k-th smallest element in a Binary Search Tree (BST). At first glance, this problem may look like a simple tree traversal problem, but the key insight lies in understanding the special property of a BST.

In a BST, an inorder traversal (Left → Root → Right) always visits nodes in sorted order. This property allows us to avoid unnecessary sorting and directly access the k-th smallest element during traversal.

---

💡 Initial Thought Process

My first approach was straightforward:

• Traverse the entire tree
• Store all values in a list
• Sort the list
• Return the k-th smallest element

While this works for any binary tree, it is inefficient for a BST. Once I realized the tree is a BST, I shifted my approach to use inorder traversal, which naturally gives sorted values.

---

🌳 Recursive Inorder Traversal Approach

The idea is to perform an inorder traversal and count nodes as they are visited. Once the count reaches k, we store the result and stop further traversal.

One of the main challenges here is breaking the recursion early. Simply finding the answer is not enough—every recursive call must know when to stop executing.

class Solution:
    def kthSmallest(self, root, k):
        self.count = 0
        self.result = None

        def inorder(node):
            if not node or self.result is not None:
                return

            inorder(node.left)

            self.count += 1
            if self.count == k:
                self.result = node.val
                return

            inorder(node.right)

        inorder(root)
        return self.result

Here, a global flag (self.result) is used to ensure that once the answer is found, all remaining recursive calls terminate immediately.

---

📦 Iterative Inorder Traversal (Using Stack)

To better understand inorder traversal mechanics, I also explored the iterative approach using an explicit stack. This gives more control over execution and makes early termination very intuitive.

class Solution:
    def kthSmallest(self, root, k):
        stack = []
        count = 0

        while True:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                count += 1

                if count == k:
                    return root.val

                root = root.right

This approach mimics recursion internally and allows us to return immediately once the k-th node is processed.

---

⏱️ Time and Space Complexity

• Time Complexity: O(H + k), where H is the height of the tree
• Space Complexity: O(H) due to recursion stack or explicit stack

In the worst case (skewed tree), this becomes O(N), but for balanced BSTs, it is highly efficient.

---

📌 Key Takeaways

• Inorder traversal of a BST gives sorted values
• Counting during traversal avoids extra storage and sorting
• Early termination in recursion requires explicit stopping conditions
• Iterative traversal can sometimes feel more intuitive than recursion

---

🔗 Source Code

You can find the complete solution on GitHub:

👉 LC230 – Kth Smallest Element in a BST (Python Solution)