K’th Smallest Element in BST

November 4, 2023

Smallest

Kth Smallest Element in BST

Introduction

Binary Search Trees (BSTs) are versatile data structures known for their efficient searching capabilities. Beyond searching, they offer a wealth of insights into the relationships between elements within the tree. One such exploration is the quest for the K’th smallest element in a BST. This problem, commonly encountered in computer science and data analysis, involves finding the K’th element when the elements are sorted in ascending order.

Understanding the K'th Smallest Element in BST

To find the K’th smallest element in a BST, we leverage the inherent properties of BSTs. In a valid BST, elements in the left subtree are smaller than the root, while elements in the right subtree are larger.

This structural organization forms the basis for an efficient approach to finding the K’th smallest element. Before diving deep into

What is K'th Smallest Element?

The K’th smallest element in a Binary Search Tree (BST) is the K’th element when the elements of the BST are sorted in ascending order. In other words, it’s the K’th smallest value among all the values stored in the BST.

To find the K’th smallest element in a BST, you typically perform an inorder traversal of the tree. In an inorder traversal, you visit nodes in ascending order, starting from the leftmost node (the smallest value) and moving towards the right.

Example :

Given a Binary Search Tree (BST) with its root node and an integer K as input, the task is to determine the K’th smallest element in the BST.

  • For instance, consider the following BST: if K equals 3, the result would be 12, and if K is set to 5, the output would be 15.
Kth Smallest Element in BST Example

 

Approach: Inorder Traversal

    1. Inorder Traversal: The key to solving this problem lies in performing an inorder traversal of the BST. In an inorder traversal, we visit nodes in ascending order, making it ideal for finding the Kth smallest element.

    2. Counting Elements: As we traverse the tree, we keep track of the number of elements encountered. When the count reaches K, we have found the Kth smallest element.

    3. Stopping Condition: Once we find the Kth element, we can stop the traversal, as further exploration is unnecessary.

Code for K'th Smallest Element in BST

1. Using Inorder Traversal : 

Here’s a code snippet :

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

def kth_smallest(root, k):
    def inorder_traversal(node):
        nonlocal k, result
        if not node:
            return
        
        # Traverse the left subtree
        inorder_traversal(node.left)
        
        # Process the current node
        k -= 1
        if k == 0:
            result = node.val
            return
        
        # Traverse the right subtree
        inorder_traversal(node.right)
    
    result = None
    inorder_traversal(root)
    return result

# Example usage:
if __name__ == "__main__":
    root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(8)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(4)
    
    k = 3
    result = kth_smallest(root, k)
    print("The", k, "th smallest element is", result)

Output :

The 3rd smallest element is 4

Explanation :

This code defines a TreeNode class and a ‘kth_smallest‘ function that uses a recursive approach with inorder traversal to find the Kth smallest element in a BST. The inorder_traversal function is a helper function that recursively explores the left subtree, processes the current node, and then traverses the right subtree. When the Kth element is found, it updates the result variable.

2. Using Any Tree Traversal :

Let’s see the code.

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

def kth_smallest(root, k):
    def preorder_traversal(node):
        nonlocal k, result
        if not node:
            return
        
        # Process the current node
        k -= 1
        if k == 0:
            result = node.val
            return
        
        # Traverse the left subtree
        preorder_traversal(node.left)
        
        # Traverse the right subtree
        preorder_traversal(node.right)
    
    result = None
    preorder_traversal(root)
    return result

# Example usage:
if __name__ == "__main__":
    root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(8)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(4)
    
    k = 3
    result = kth_smallest(root, k)
    print("The", k, "th smallest element is", result)

Output :

The 3rd smallest element is 4.

Explanation :

This code follows a similar structure to the previous examples but uses preorder traversal to find the Kth smallest element. The output will still correctly identify the Kth smallest element in the given BST.

3. Using Stack :

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

def kth_smallest(root, k):
    stack = []
    current = root
    
    while True:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        k -= 1
        
        if k == 0:
            return current.val
        
        current = current.right

# Example usage:
if __name__ == "__main__":
    root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(8)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(4)
    
    k = 3
    result = kth_smallest(root, k)
    print("The", k, "th smallest element is", result)

Output :

The 3rd smallest element is 4.

Explanation :

This code uses an iterative approach to find the Kth smallest element in a BST. It employs a stack to simulate the recursive inorder traversal. The algorithm visits nodes in ascending order and keeps track of the count until it reaches the Kth smallest element. In the example, it finds and prints the 3rd smallest element, which is 4. This method efficiently traverses the tree while minimizing memory usage.

Significance of Finding K'th Smallest Element in BST

Discovering the Kth smallest element in a BST is crucial in various scenarios:

  • Statistics: In statistical analysis, it helps identify percentiles or values below which a certain percentage of data falls.

  • Database Queries: In databases, it aids in efficient retrieval of sorted data, especially in scenarios like finding the top K results.

  • Data Analysis: It is valuable in data analysis tasks where understanding data distribution or outliers is necessary.

  • Algorithms: Solving this problem has applications in algorithm design, such as finding the median element or implementing priority queues efficiently.

Complexity analysis for K'th smallest Element in BST

The complexity analysis for finding the Kth smallest element in a Binary Search Tree (BST) involves examining both time and space complexity.

Time Complexity:

  1. Inorder Traversal (Recursive): The time complexity for this approach is O(N), where N is the number of nodes in the BST. In the worst case, you may have to visit all nodes to find the Kth smallest element.

  2. Inorder Traversal (Iterative): The time complexity remains O(N) in the iterative approach as well. It also requires visiting all nodes.

  3. Morris Traversal: Morris Traversal also has a time complexity of O(N), where N is the number of nodes in the BST. It is a linear time complexity algorithm because it visits each node at most twice.

Space Complexity:

  1. Inorder Traversal (Recursive): The space complexity for the recursive approach is O(H), where H is the height of the BST. In the worst case, when the BST is skewed, the space complexity is O(N).

  2. Inorder Traversal (Iterative): The iterative approach using a stack has a space complexity of O(H) as well, where H is the height of the BST. It requires additional space to store the stack.

  3. Morris Traversal: Morris Traversal has a space complexity of O(1). It is memory-efficient and doesn’t require additional data structures like stacks or recursion.

To wrap it up:

The quest for the Kth smallest element in a Binary Search Tree combines the elegance of BST traversal with practical applications in data analysis and algorithm design. Understanding this problem not only enhances your grasp of BSTs but also equips you with a powerful tool for navigating and extracting meaningful insights from sorted datasets.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Question 1.

How do I find the Kth smallest element in a BST?

You can find the Kth smallest element in a BST by performing an inorder traversal of the tree while keeping track of the count of visited nodes. When the count reaches K, you have found the Kth smallest element.

Question 2.

Is it possible to find the Kth smallest element without using extra memory (e.g., stacks or recursion)?

Yes, you can use Morris Traversal, which allows you to find the Kth smallest element without using additional memory. This approach modifies the tree structure temporarily to create threads between nodes.

Question 3.

Can I find the Kth smallest element in an unbalanced BST?

Yes, you can find the Kth smallest element in an unbalanced BST. However, the time complexity may be closer to O(N) in the worst case due to the lack of balance.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout