---
tags: data_structure_python
---

# Kth Smallest Element in a BST <img src="https://img.shields.io/badge/-easy-brightgreen">

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

**Example 1:**

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

**Example 2:**

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

**Follow up:**

What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

**Constraints:**

- The number of elements of the BST is between 1 to 10^4.
- You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

## Solution

### Solution 1: Recursive 1

Inorder traversal in a BST outputs sorted list.

# Definition for a binary tree node.
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: TreeNode, k: int) -> int:
        # n = # of nodes in BST.
        # Time complexity: O(n).
        # Space complexity: O(n).
        def dfs(root, res):
            if root != None:
                dfs(root.left, res)
                res.append(root.val)
                dfs(root.right, res)
                
        res = []
        dfs(root, res)
        return res[k-1]

### Solution 2: Iterative 1

- Time complexity: O(n).
- Space complexity: O(n).

# Definition for a binary tree node.
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: TreeNode, k: int) -> int:
        # Time complexity: O(n).
        # Space complexity: O(n).
        stack, res = [(root, False)], []
        
        while len(stack) > 0:
            node, visited = stack.pop()
            if node != None:
                if visited:
                    res.append(node.val)
                else:
                    stack.append((node.right, False))
                    stack.append((node, True))
                    stack.append((node.left, False))
        return res[k-1]

### Solution 3: Iterative 2

- Time complexity: O(n).
- Space complexity: O(n).

# Definition for a binary tree node.
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: TreeNode, k: int) -> int:
        # Time complexity: O(n).
        # Space complexity: O(n).
        stack = [(root, False)]
        
        while len(stack) > 0:
            node, visited = stack.pop()
            if node != None:
                if visited:
                    k -= 1
                    if k == 0:
                        return node.val
                else:
                    stack.append((node.right, False))
                    stack.append((node, True)) # Inorder.
                    stack.append((node.left, False))
        return None