
class Solution {
    private int count = 0;
    private int result = 0;

    public int kthSmallest(TreeNode root, int k) {
        inOrderTraversal(root, k);
        return result;
    }

    private void inOrderTraversal(TreeNode node, int k) {
        if (node == null || count >= k) {
            return;
        }

        // Traverse the left subtree
        inOrderTraversal(node.left, k);

        // Process the current node
        count++;
        if (count == k) {
            result = node.val;
            return;
        }

        // Traverse the right subtree
        inOrderTraversal(node.right, k);
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

The "Kth Smallest Element in a Binary Search Tree (BST)" problem asks for finding the kth smallest element in a Binary Search Tree. Since a BST is sorted in order (left subtree contains smaller values, and right subtree contains larger values), the kth smallest element can be efficiently found using an in-order traversal. The in-order traversal of a BST produces nodes in ascending order.

Problem Statement

Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest element in the BST. Note that the kth smallest element is 1-indexed, so for example, the 1st smallest element would be the smallest element in the tree.

The goal is to return the kth smallest element in the BST using efficient traversal methods.

Approach

To solve this problem, we can use an in-order traversal of the BST. The key observation is that the nodes in a BST are visited in ascending order during in-order traversal. Thus, by performing an in-order traversal and counting nodes visited, we can return the kth smallest element once we've visited k nodes.

Perform an in-order traversal of the BST.
Track the number of nodes visited during traversal.
When the kth node is reached, return its value.
Stop the traversal early once the kth smallest element is found to save computation.

Algorithm

The algorithm follows these steps:

Define a helper function that performs an in-order traversal of the tree and returns the kth smallest element.
Start the in-order traversal from the root, and use a counter to track the number of nodes visited.
When the kth node is visited, store its value and return it.
If the kth smallest element is found, the traversal can be terminated early.

This approach allows us to stop the traversal as soon as the kth smallest element is found, making it efficient.

Example

Consider the following Binary Search Tree:

If k = 3, the in-order traversal of this tree is [2, 3, 4, 5, 6]. Therefore, the 3rd smallest element is 4.

Thus, the solution should return: - 4

Code Implementation

Below is the Python implementation of the algorithm to find the kth smallest element in a Binary Search Tree:

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because we perform an in-order traversal of the entire tree to collect all the elements.

The space complexity is also O(n), where n is the number of nodes in the tree, as we store the entire tree’s elements in the sorted list during the in-order traversal.

Optimized Approach

The approach above has O(n) space complexity due to storing all elements in a list. However, we can optimize this by performing the in-order traversal and counting the nodes without storing all of them. Once we reach the kth element, we can return it immediately.

In this optimized approach: - We perform the in-order traversal, incrementing a counter as we visit each node. - Once we visit the kth node, we immediately return its value and stop the traversal early, saving computation time. - This reduces the space complexity to O(h), where h is the height of the tree (the space used by the recursion stack).

Time Complexity (Optimized)

The time complexity remains O(n), where n is the number of nodes in the tree, because we may still need to visit each node to find the kth smallest element.

The space complexity is reduced to O(h), where h is the height of the tree, due to the recursion stack used in the in-order traversal. In the worst case (a skewed tree), the height of the tree is O(n), but in the best case (a balanced tree), the height is O(log n).

Conclusion

The "Kth Smallest Element in a Binary Search Tree" problem is a great example of utilizing in-order traversal to exploit the sorted nature of BSTs. The standard approach involves performing an in-order traversal and returning the kth smallest element from the sorted list. An optimized approach allows us to stop the traversal once the kth element is found, reducing unnecessary work and space usage.