Kth Smallest Element In A BST Leetcode Problem 230 [Python Solution]

If you're here, you're probably looking for a solution to the Kth Smallest Element in a Binary Search Tree problem on LeetCode.

Well, you've come to the right place!

In this blog post, we'll walk you through the problem, discuss the constraints, explore different approaches, and provide a Python solution to help you ace this challenge.

Problem Overview

The problem statement is as follows:

Question Link: Kth Smallest Element In a BST on LeetCode

You are given the root of a binary search tree (BST) and an integer k.

Your task is to find and return the kth smallest element in the BST, where k is 1-indexed.

To better understand this problem, let's consider an example.

Example 1:

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

Output:
1

In this example, the BST looks like this:
3 / 1 4

2

If we list the values of the nodes in ascending order, we get [1, 2, 3, 4].

The 1st smallest element is 1, which is the expected output.

Constraints:

The number of nodes in the tree is n.
1 <= k <= n <= 104
0 <= Node.val <= 104

Understanding BST Constraints

Before we dive into the solution, it's important to understand the constraints and properties of a Binary Search Tree (BST).

A BST is a binary tree in which, for each node:

All nodes in its left subtree have values less than the node's value.
All nodes in its right subtree have values greater than the node's value.

These properties make it easier to find the kth smallest element because we know that smaller elements will always be on the left side of the tree, and larger elements will be on the right.

Kth Smallest Element In a BST LeetCode Problem Solution

1. Bruteforce Approach

One way to approach this problem is to perform an in-order traversal of the BST to collect all elements in ascending order, and then return the kth element.

However, this approach is not efficient for large trees and may not be optimal for this problem.

Here's a simple Python code snippet for this bruteforce approach:

def kthSmallest(root, k):
    elements = []

    def inorder(node):
        if not node:
            return
        inorder(node.left)
        elements.append(node.val)
        inorder(node.right)

    inorder(root)
    return elements[k - 1]

This code performs an in-order traversal of the BST, adding each element to the elements list.

After traversal, it returns the k-th element from the list.

While this approach is straightforward, it has a time complexity of O(n), where n is the number of nodes in the tree.

2. An Efficient Approach with Stack

The bruteforce approach, although correct, is not optimal.

We can achieve better performance with an iterative approach using a stack to simulate the in-order traversal.

Here's a more efficient Python solution:

View on GitHub ➹

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def kthSmallest(root, k):
    stack = []
    curr = root

    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        k -= 1
        if k == 0:
            return curr.val
        curr = curr.right

This code defines a TreeNode class for the tree structure and uses a stack to perform an in-order traversal of the BST.

The key idea is to keep traversing left as far as possible and pop nodes from the stack when we're done with their left subtrees.

We decrement k with each visited node and return the result when k reaches 0. This approach has a time complexity of O(h + k), where h is the height of the tree.

In a balanced BST, the height h is approximately log(n), making this solution efficient for large trees.

Time and Space Complexity

Time Complexity

In the bruteforce approach, the time complexity is O(n), where n is the number of nodes in the tree.
In the efficient approach using a stack, the time complexity is O(h + k), where h is the height of the tree.

In a balanced BST, the height h is approximately log(n), making this approach efficient.

Space Complexity

In the bruteforce approach, the space complexity is O(n) due to the list used to store elements during traversal.
In the efficient approach using a stack, the space complexity is O(h) due to the stack used for traversal.

This is because the stack only holds the nodes along the left path from the root to the current node.

Reasoning Behind Our Approach

The efficient stack-based approach provides a more optimized solution for the Kth Smallest Element in a BST problem compared to the bruteforce method.

Here's the reasoning behind this approach:

We leverage the properties of a Binary Search Tree (BST) to determine which subtrees to explore.

The in-order traversal, visiting left nodes first and then their parent and right nodes, ensures that we encounter nodes in ascending order.

By using a stack, we mimic the recursive process of the in-order traversal iteratively.

The stack keeps track of the nodes to visit and ensures we can easily backtrack to the parent node when needed.

We continue the traversal until k reaches 0, which means we have found the k-th smallest element.

At this point, we return the value of the current node.

This approach has a time complexity of O(h + k), where h is the height of the tree.

In a balanced BST, the height is log(n), making this solution efficient even for large trees.

Conclusion

In this blog post, we've tackled the Kth Smallest Element in a Binary Search Tree problem from LeetCode.

We discussed the problem statement, constraints, and two different approaches to solve it.

The efficient approach using a stack provides an optimal solution with a time complexity of O(h + k), making it suitable for large BSTs.

If you found this guide helpful, please like and engage to support our our platform.

If you have any questions, suggestions, or comments, feel free to share them below.

We hope this solution helps you in your coding journey, and best of luck with your coding challenges!