Kth Smallest Element in a BST

Problem Statement

In this task, you are given the root node of a binary search tree (BST) and an integer k. The goal is to determine and return the kth smallest element in the tree. It's important to recognize that the values in each node of a BST follow a specific order: for any given node, the values in its left subtree are lesser, and the values in its right subtree are greater. This intrinsic ordering of BSTs is essential for efficiently finding the kth smallest element, especially considering the constraints provided.

Examples

Example 1

Input:

root = [3,1,4,null,2], k = 1

Output:

1

Example 2

Input:

root = [5,3,6,2,4,null,null,1], k = 3

Output:

3

Constraints

• The number of nodes in the tree is n.
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

Approach and Intuition

To solve the problem of finding the kth smallest element in a binary search tree, consider the following logical steps:

1. In-Order Traversal: In a BST, an in-order traversal (left-root-right) yields elements in non-decreasing order. This property makes in-order traversal particularly suitable for this problem since accessing the kth element directly gives the kth smallest value.

2. Recursive Traversal with Early Stopping: While performing the in-order traversal:

   • If the traversal reaches the kth element, you can stop further traversal. This enhances efficiency by not traversing the entire tree if not necessary.

3. Using an Auxiliary Data Structure:

   • You could use an array to store in-order traversal results and then directly access the kth - 1 index to retrieve the kth smallest value. However, this might not be the most space-efficient method as it requires storing potentially many node values.

4. Iterative Deepening:

   • This involves using an iterative approach with a stack to simulate the recursive in-order traversal. This bypasses the potential stack overflow issue with deep recursion trees and usually offers more control over the traversal sequence, allowing easy retrieval of the kth element.

Examples Clarification:

• For instance, in the first example, performing an in-order traversal on the tree rooted at [3,1,4,null,2] gives the sequence [1,2,3,4]. The first element (1-indexed) would be 1.
• In the second example, the same in-order traversal on the tree rooted at [5,3,6,2,4,null,null,1] yields [1,2,3,4,5,6]. The third element in this ordered sequence is 3.

These examples show how following the in-order traversal and then selecting the kth element from the resultant ordered list give the required result, adhering to the constraints given. Each node's value and the range of k within the total number of elements ensure the method's applicability for all valid inputs up to the defined limits.

Solutions

class Solution {
  public int findKthSmallest(TreeNode root, int k) {
    Stack<TreeNode> treeStack = new Stack<>();

    while (true) {
      while (root != null) {
        treeStack.push(root);
        root = root.left;
      }
      root = treeStack.pop();
      if (--k == 0) return root.val;
      root = root.right;
    }
  }
}

class Solution:
    def findKthSmallest(self, node: Optional[TreeNode], position: int) -> int:
        nodes = []
        
        while True:
            while node:
                nodes.append(node)
                node = node.left
            node = nodes.pop()
            position -= 1
            if position == 0:
                return node.val
            node = node.right