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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Kth Smallest Element in a BST

Difficulty: Medium

Problem Description

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

Key Insights

  • A binary search tree (BST) is a tree where the left child is less than the parent and the right child is greater.
  • In-order traversal of a BST yields the values of the nodes in ascending order.
  • The k-th smallest element can be found by performing an in-order traversal and counting the nodes visited until reaching k.

Space and Time Complexity

Time Complexity: O(H + k), where H is the height of the tree. In the worst case, for a skewed tree, this could be O(n) where n is the number of nodes. Space Complexity: O(H) for the recursion stack, which can also be O(n) in the worst case for a skewed tree.

Solution

To find the k-th smallest element in a BST, we can utilize an in-order traversal approach. We traverse the tree in a left-root-right order, counting the nodes as we visit them. When we reach the k-th node, we can return its value. This method efficiently allows us to find the k-th smallest element without needing to store all elements in memory, leveraging the properties of the BST.

Code Solutions

def kthSmallest(root, k):
    # Helper function to perform in-order traversal
    def in_order_traversal(node):
        if not node:
            return []
        return in_order_traversal(node.left) + [node.val] + in_order_traversal(node.right)

    # Perform in-order traversal and retrieve the k-th smallest element
    return in_order_traversal(root)[k - 1]
← Back to All Questions