Kth Largest in a Binary Search Tree 🎯

Welcome to a comprehensive guide on finding the Kth largest element in a Binary Search Tree (BST)! This lesson is designed to help both beginners and intermediates understand this important concept in data structures and algorithms. Let's dive right in!

Understanding Binary Search Tree (BST) 📝

A Binary Search Tree (BST) is a binary tree data structure where each node has at most two children: left and right. It maintains the following properties:

The key of the left child is less than the parent node.
The key of the right child is greater than or equal to the parent node.
There are no duplicate keys in the BST.

Finding Kth Largest in a BST 💡

Now, let's focus on finding the Kth largest element in a BST. This problem can be solved using a Morris Inorder Traversal or Inorder Traversal with an extra variable.

Morris Inorder Traversal Approach 🎯

Morris Inorder Traversal is a space-efficient inorder traversal of binary tree that does not use a stack. Here's how it works:

Start from the root node.
If the current node is null, return.
If the current node has no right child, visit the current node, then move to the left child.
If the current node has a right child, find the inorder predecessor (the rightmost node in the left subtree) and make it the right child of the parent of the current node. Then visit the current node, and make it the left child of the inorder predecessor.

Inorder Traversal with an Extra Variable Approach 🎯

This approach uses an extra variable 'k' to keep track of the Kth largest element. It performs an inorder traversal and updates 'k' as needed.

Initialize 'k' with the total number of nodes.
Perform an inorder traversal of the BST.
Update 'k' whenever we encounter a new node. If 'k' becomes zero, we have found the Kth largest element.

Code Examples ✅

Morris Inorder Traversal

python

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

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

    while current:
        if not current.left:
            count += 1
            if count <= k:
                k -= count == k
                print(current.key, end=" ")

        prev = current
        current = current.left
        if not current:
            current = prev.right
            prev.right = prev.left
            prev.left = current

### Inorder Traversal with an Extra Variable

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

    def inorder(node):
        nonlocal current, count
        if node:
            inorder(node.left)
            count -= 1 if count > 0 and count <= k else 0
            if count > 0:
                print(node.key, end=" ")
            inorder(node.right)

    inorder(current)

Quiz 📝

That's it for today! In the next lesson, we will explore more advanced applications of finding the Kth largest element in a BST. Until then, happy coding! 🚀