Leetcode 230. Kth Smallest Element in a BST

Problem

Leetcode 230 - Kth Smallest Element in a BST

Example:

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

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

Approach

We can use In-order traversal then return k-1’th that we interact with.

Here is the Python code for the solution:

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        res = []
        def dfs(root):
            if not root:
                return
            
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        
        return res[k-1]
    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$