Technical Interview Question:

Given a binary search tree (BST), write a function to find the Kth smallest element in the tree.

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

def kth_smallest_element(root, k):
    # Your code here

Answer:

def kth_smallest_element(root, k):
    stack = []
    curr = root

    while True:
        while curr is not None:
            stack.append(curr)
            curr = curr.left

        curr = stack.pop()
        k -= 1
        if k == 0:
            return curr.value
        curr = curr.right

1. We start with an empty stack and set the current node to the root of the BST.
2. We traverse the left child of the current node and keep adding nodes to the stack until we reach the leftmost node.
3. Once we reach the leftmost node, we pop the top element from the stack and decrement the value of k by 1. If k becomes 0, we return the value of the popped element (which is the kth smallest element in the BST).
4. If k is not 0, we move to the right child of the popped element and continue the process from step 2.
5. We repeat this process until we have found the kth smallest element or the stack becomes empty.