algoadvance

Leetcode 230. Kth Smallest Element in a BST

Problem Statement

Given the root of a binary search tree (BST) and an integer k, return the k-th smallest element in the tree.

Example:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Clarifying Questions

1. Q: Can the values in the BST be negative and positive? A: Yes, values can be any integer.

2. Q: Can we assume that k is always valid, i.e., 1 <= k <= number of nodes in the BST? A: Yes, you can assume that k is always valid.

3. Q: What is the maximum number of nodes in the BST? A: The number of nodes is 10^4 as per typical constraints.

4. Q: Should the solution be optimized for space or time complexity? A: A balanced approach is preferred, though typically time complexity is emphasized.

Strategy

To find the k-th smallest element in a BST, we can leverage the properties of the tree:

1. In-order Traversal: Performing an in-order traversal (left, root, right) on a BST yields elements in sorted order.

We will keep track of the number of elements processed and return the k-th element during the traversal.

Code

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */

public class Solution {
    private int count = 0;
    private int result = -1;

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

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

        inOrderTraversal(node.left, k);

        count++;
        if (count == k) {
            result = node.val;
            return;
        }

        inOrderTraversal(node.right, k);
    }
}

Time Complexity

• Time Complexity: O(N) in the worst case, where N is the number of nodes in the BST, as we might need to traverse all nodes in the tree.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursion stack. In the best case of a balanced tree, H = O(log N). In the worst case, H can be O(N) for a completely unbalanced tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?