Problem Statement in English

You’re given a binary search tree. Your task is to return the kth smallest element in it. The tree is 1 indexed. The element at the bottom left is index 1.

Approach

This is basically a depth first search. You go left as far as you can, when you can’t, you go back up, and go right whenever possible on your way back up. It can be done either iteratively or recursively.

I chose to go with the recursive approach, but the iterative one is actually much cleaner for this particular question.

We also don’t need to keep track of what’s minimum and all that. Since it’s a BST, this traveral (inorder) goes from the smallest to largest element.

Step 1: Go as far left as we can

  • Step 1.1: When you can’t go left anymore…
    Check if the current ID is the required one, if it is just bubble state back up the tree.

Step 2: Go up

  • Step 2.1: Check if the current state is the solution
    If it is, just bubble the state back up the tree.

  • Step 2.2: Check if going one node up is the required solution
    If it is, go up and bubble the new state at that node (increment ID by one, and update val to be the val at that node) back up the tree.

Step 3: Go right when possible

  • Step 3.1: If you can go right, go right
    Recursively call the function to traverse the subtree in inorder again.

Solution in Python


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


class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        # to get my editor to stop screaming at me
        assert root != None

        # the recursive solution
        return self.recursiveSearch(root, k, state=[0, -1])[1]

    # i use `state` to propagate data up and down the tree.
    # [current index, current value]
    def recursiveSearch(
        self, root: TreeNode, target: int, state: List[int]
    ) -> List[int]:

        # base case
        # if it's a deadend, increment the id, and update val to be that of the current node
        if root.left is None and root.right is None:
            return [state[0] + 1, root.val]

        # copy state into a new var
        final = state

        # if we can go left
        if root.left is not None:
            # go left!
            final = self.recursiveSearch(root.left, target, state=final)

        # we can't go left any further

        # check if going up one node is the index we need
        # if it is, do it
        if final[0] + 1 == target:
            # return this solution as it is the required one
            return [final[0] + 1, root.val]

        # check if this current node is the required solution
        elif final[0] == target:
            # if it is, return it
            return final

        # keep going up, and right when possible
        else:
            # increment the current id we're at
            # update val to be that of the current node
            final = [final[0] + 1, root.val]

            # if we can go right
            if root.right is not None:
                # go righ!
                final = self.recursiveSearch(root.right, target, state=final)

            # else return state and bubble back up the tree
            return final

Complexity

  • Time: O(n)O(n)
    In the worst case, we travel all nodes in the tree, which is n.

  • Space: O(n)O(n)
    We use a recursion stack, which can grow to the number of nodes in the tree, which is n.

Mistakes I Made

I forgot to write the base case 🤦‍♂️.

And we are done.