Kth Smallest in Binary Search Tree 🎯

Welcome back to CodeYourCraft! Today, we're diving into one of the fundamental concepts of algorithms - finding the Kth smallest element in a Binary Search Tree (BST). This is a crucial skill for any programmer and will be useful in various real-world projects.

Let's start by understanding what a Binary Search Tree (BST) is.

Binary Search Tree (BST) 📝

A Binary Search Tree is a data structure that organizes data in nodes. Each node has a key and up to two children (left and right). The keys in the left subtree are less than the parent node, and the keys in the right subtree are greater than the parent node. This organization allows for efficient search, insertion, and deletion operations.

Binary Search Tree

Finding the Kth Smallest Element 💡

The task is to find the Kth smallest element in a given BST. For this, we'll use the Morris Traversal algorithm, which is an in-place, iterative approach for traversing a BST.

Here's a step-by-step breakdown of the algorithm:

Current: Start from the root of the tree.
If the current node is null, we return.
Visit the current node (we'll see how to do this later).
Go to the right child of the current node (if it exists).
While the right child is not null, we perform a special maneuver:
1. Make the right child's right child the successor.
2. Make the current node the right child of the successor.
3. Now, the current node is the successor's left child (if it exists).

Implementing the Algorithm 💡

Let's implement the Morris Traversal for finding the Kth smallest element.

python

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

k = 3  # Kth smallest element to find
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)

def kthSmallest(root, k):
    current = root
    count = 0

    while current:
        if not current.left:
            count += 1
            if count == k:
                print("Kth smallest element is", current.val)
                return
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                current = current.left
            else:
                count += 1
                if count == k:
                    print("Kth smallest element is", current.val)
                    return
                current = None
                current = current.right

kthSmallest(root, k)

In this implementation, we define a Node class and create a BST. Then, we define a recursive function kthSmallest to find the Kth smallest element using the Morris Traversal algorithm.

📝 Note: The Morris traversal visits each node exactly twice, once when traversing from left to right and once when traversing from right to left, but the second visit happens through a different path, making it an in-place traversal.

Quiz 🎯

Conclusion 🎯

We've learned about Binary Search Trees and the Morris Traversal algorithm to find the Kth smallest element in a BST. This concept is fundamental for any programmer and will be useful in various projects.

Stay tuned for more engaging and educational lessons at CodeYourCraft! 🚀🚀🚀