Kth Smallest Element in a BST medium

Problem Statement

Given the root of a binary search tree (BST) and an integer k, return the k^th smallest element in the BST. You can assume k is always valid, 1 ≤ k ≤ total nodes of the BST.

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

Steps

The most efficient approach to solve this problem leverages the inherent properties of a Binary Search Tree (BST). A BST is ordered: an inorder traversal will visit nodes in ascending order. Therefore, we can perform an inorder traversal and track the kth element encountered. This avoids the need for sorting or maintaining a large data structure.

1. Inorder Traversal: Implement an inorder traversal recursively or iteratively.
2. Counter: Maintain a counter to track the number of nodes visited during the traversal.
3. Return kth element: When the counter reaches k, return the current node's value.

Explanation

The inorder traversal systematically visits the left subtree, then the root, then the right subtree. Because of the BST property, this guarantees that nodes are visited in ascending order. We simply need to stop the traversal once we've visited k nodes.

Code (Java)

import java.util.*;

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

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

    private void inorderTraversal(TreeNode root, int k) {
        if (root == null || count >= k) return; // Base cases: empty subtree or kth element found

        inorderTraversal(root.left, k); // Visit left subtree

        count++; // Increment counter
        if (count == k) {
            result = root.val; // Store the kth smallest element
            return; // Exit early
        }

        inorderTraversal(root.right, k); // Visit right subtree
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Complexity

• Time Complexity: O(H + k), where H is the height of the BST. In the worst case (a skewed tree), H could be N (number of nodes), resulting in O(N) time complexity. However, for balanced BSTs, H is log N, leading to O(log N + k) which is approximately O(log N) if k is relatively small compared to N.
• Space Complexity: O(H) in the worst case due to the recursive call stack. For a balanced BST, this becomes O(log N). An iterative approach could reduce space complexity to O(1).