Kth Smallest Element in a Binary Search Tree

Given a binary search tree (BST), find the kth smallest element in it.

Function Signature:

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

def kth_smallest(root: TreeNode, k: int) -> int:
    """
    Finds the kth smallest element in the binary search tree.

    Parameters:
    - root: The root node of the binary search tree.
    - k: The kth smallest element to find.

    Returns:
    - int: The value of the kth smallest element.
    """
    # Your code here

Example:

# Example 1:
#        3
#       / \
#      1   4
#       \
#        2
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
result = kth_smallest(root, 1)
print(result)  # Output should be 1

# Example 2:
#         5
#        / \
#       3   6
#      / \
#     2   4
#    /
#   1
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)
result = kth_smallest(root, 3)
print(result)  # Output should be 3

Note:

• You can assume k is always valid, 1 ≤ k ≤ BST’s total elements.
• The BST is defined as follows:
  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Instructions:

• Implement the kth_smallest function to solve the problem.
• Utilize the provided TreeNode class to represent nodes in the binary search tree.
• Use Python for your implementation.
• Provide clear comments in your code to explain the logic.
• Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊