LC 230. Kth Smallest Element in a BST

LC 230. Kth Smallest Element in a BST

In this article, we will analyze the LeetCode problem "Kth Smallest Element in a BST". Let's start with the problem statement.

Problem Statement:

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

Kth Smallest Element in a BST - Example 1
Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Kth Smallest Element in a BST - 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:

We can leverage the properties of Binary Search Trees (BSTs) to find the kth smallest element. In a BST, nodes are organized such that:
  • All values in the left subtree of a node are smaller than the node's value.
  • All values in the right subtree are larger.
To find the kth smallest element, we can traverse the tree in an in-order manner (left-root-right), which naturally processes the nodes in ascending order. Depth First Search (DFS) is an effective strategy for this traversal.

Steps:

  1. Initialize State: Create a state dictionary to keep track of the current node count and the result.
  2. Define DFS Function: Implement a DFS function that prioritizes the left nodes.
  3. Traverse the Tree: Use the DFS function to traverse the tree and update the state.
  4. Return Result: Continuously check the state, as soon as the count equals k return the res from the state.

Solution:

Here is the Python implementation of the solution:

kthSmallestElement.py

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        state = {'c': 0, 'res': -1}
        
        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            state['c'] += 1
            if state['c'] == k:
                state['res'] = node.val
                return  # No need to continue once the kth smallest is found
            dfs(node.right)
        
        dfs(root)
        return state['res']
  1. State Initialization: We use a dictionary state to keep track of the current count of visited nodes (c) and the result (res).
  2. DFS Traversal:
    • Traverse the left subtree.
    • Increment the count when visiting the current node.
    • If the count equals k, store the node's value in res and terminate further traversal.
    • Traverse the right subtree.
  3. Return Result: After completing the DFS, the kth smallest element is stored in state['res'].

Complexity Analysis:

This approach finds the kth smallest element in a BST with a time complexity of O(H + k), where H is the height of the tree, and k is the index of the smallest element to find. The space complexity is O(H) due to the recursion stack.