We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Kth Smallest Element in a BST

Number: 230

Difficulty: Medium

Paid? No

Companies: Amazon, Uber, Google, Meta, Bloomberg, Oracle, Microsoft, LinkedIn, Cisco, Apple, Adobe, Expedia, Yahoo, Agoda

Problem Description

Given the root of a binary search tree (BST) and an integer k, return the kth smallest value in the BST (1-indexed). Since an in-order traversal of a BST naturally retrieves the nodes in sorted order, we can leverage this property to efficiently solve the problem.

Key Insights

  • An in-order traversal of a BST visits nodes in increasing order.
  • Use a counter to keep track of the number of nodes visited.
  • As soon as the counter reaches k, the current node’s value is the kth smallest.
  • For frequent modifications (insertions/deletions) and queries, consider augmenting the BST with subtree counts.

Space and Time Complexity

Time Complexity: O(n) in the worst-case scenario (when k ≈ n), but on average the traversal may stop early. Space Complexity: O(h) where h is the height of the tree (O(n) in the worst-case for a skewed tree).

Solution

We perform an in-order traversal of the BST which visits nodes in ascending order. During the traversal, we maintain a counter (or decrement k) to check when we have encountered the kth smallest element. When the counter reaches 0 (or k becomes 0), we capture the current node’s value as our answer and return it. This approach is both simple and efficient for the given constraints.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        # Initialize counter and result
        self.k = k
        self.ans = None
        
        # In-order traversal: left -> node -> right
        def inorder(node):
            if not node:
                return
            # Traverse left subtree
            inorder(node.left)
            # Process current node
            self.k -= 1
            if self.k == 0:
                self.ans = node.val
                return
            # Traverse right subtree if kth element not found
            inorder(node.right)
        
        inorder(root)
        return self.ans
← Back to All Questions