Find K-th smallest element in BST

Problem Overview

The problem titled "Kth Smallest Element in a BST" on LeetCode requires us to find the k-th smallest element in a Binary Search Tree (BST). The function should traverse the BST and return the value of the node that is the k-th smallest when the nodes are ordered by value.

Link to Problem: Kth Smallest Element in a BST

Understanding the Problem

Given a Binary Search Tree and an integer k, we need to determine the k-th smallest element in the BST. A BST is a data structure with the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both left and right subtrees are also Binary Search Trees.

For example, consider the following BST and k = 3:

      5
     / \
    3   6
   / \
  2   4
 /
1

The in-order traversal of this tree (1, 2, 3, 4, 5, 6) would lead us to find that the 3rd smallest element is 3.

Key DSA Concepts and Theory

Binary Search Tree

A Binary Search Tree (BST) is a node-based binary tree data structure where each node has a comparable key and satisfies the binary search tree condition. The average time complexity for search, insertion, and deletion operations are O(log n) where n is the number of nodes in the tree.

In-Order Traversal

To solve this problem, an understanding of in-order traversal is crucial. In-order traversal of a BST yields nodes in non-decreasing order. Here is the sequence:

1. Recursively visit the left subtree.
2. Visit the root node.
3. Recursively visit the right subtree.

By performing an in-order traversal, we can retrieve elements in sorted order and easily find the k-th smallest element.

Solution Approach

The optimal approach for this problem is to perform an in-order traversal of the BST and count the nodes until we reach the k-th node.

Step-by-Step Solution

1. Initialize Count: Start with a counter set to zero.
2. Traverse the Tree: Use a helper function to traverse the BST in in-order fashion.
3. Check Counter: During traversal, increment the counter. If the counter equals k, record the current node's value as the result.
4. Return Result: Return this stored result value.

Below are the implementations in C++ and Java.

C++ Solution

#include <iostream>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int count = 0;
        int result = -1;
        inorder(root, k, count, result);
        return result;
    }

    void inorder(TreeNode* node, int k, int &count, int &result) {
        if (node == NULL || count >= k) return;

        inorder(node->left, k, count, result);

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

        inorder(node->right, k, count, result);
    }
};

Java Solution

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

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

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

        inorder(node.left, k);

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

        inorder(node.right, k);
    }
}

Time and Space Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the BST. In the worst case, we might need to visit all nodes.
• Space Complexity: O(H), where H is the height of the tree. This space is used for the recursion stack. For balanced trees, H = O(log N), but in the worst case (skewed tree), H can be O(N).

Common Mistakes to Avoid

1. Incorrect Base Cases: Ensure your base case correctly handles NULL nodes to prevent unnecessary recursion and to avoid accessing invalid memory.
2. Counter Mismanagement: Keep careful track of your counter to ensure you don't miss or double count any nodes.
3. Assumption of a Balanced Tree: While average operations can be O(log N), always plan for the worst-case scenario, particularly with space complexity on skewed trees.

Similar Problems on LeetCode

• LeetCode 230: Kth Smallest Element in a BST (a direct variant)
• LeetCode 783: Minimum Distance Between BST Nodes

Additional Resources and References

• Binary Search Tree on Wikipedia
• In-order Traversal Concept

By understanding these concepts and following a systematic approach, you will be able to solve this problem efficiently and accurately.