Python Program to Find the Kth Smallest Element in a BST

This program defines a Binary Search Tree (BST) and a method to find the kth smallest element within it using an in-order traversal. The BST nodes are defined with the class TreeNode, each having a value and pointers to left and right child nodes.

class TreeNode:
    """Node of a Binary Search Tree."""
    def __init__(self, x):
        """
        Initialize the tree node.
        
        :param x: int, the integer value of the node
        """
        self.val = x
        self.left = None
        self.right = None

class Solution:
    """Solution class to handle tree operations."""
    def kthSmallest(self, root, k):
        """
        Find the kth smallest element in a BST.
        
        :param root: TreeNode, the root node of the BST
        :param k: int, the 'kth' position to find the smallest element
        :return: int, the kth smallest element in the BST
        """
        # Array to store the in-order traversal
        elements = []
        
        # Helper function to perform in-order traversal
        def in_order_traverse(node):
            """Recursive in-order traversal to access BST in sorted order."""
            if not node:
                return
            in_order_traverse(node.left)
            elements.append(node.val)
            in_order_traverse(node.right)
        
        # Perform the in-order traversal of the tree
        in_order_traverse(root)
        
        # Return the kth smallest element
        return elements[k-1] if k <= len(elements) else None

# Example Usage
if __name__ == "__main__":
    # Create a BST
    root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(6)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(4)
    root.left.left.left = TreeNode(1)
    
    # Instance of Solution
    sol = Solution()
    
    # Find 3rd smallest element
    kth_smallest = sol.kthSmallest(root, 3)
    print(f"The 3rd smallest element in the BST is: {kth_smallest}")

The above program initializes a basic BST and finds the kth smallest element. The Solution class contains the method kthSmallest, which performs an in-order traversal of the BST, collecting elements in a list in their inherent sorted order. The kth smallest element is then accessed directly from the list.