LeetCode #230 Kth Smallest Element in a BST

Medium

Problem

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

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

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?

Solution — Recursion

By using in-order traversal, we can easily find out the k-th smallest element in BST by counting the traversed nodes. Recursion approach can be implemented by top-down and bottom-up manners.

Complexity

Time complexity for both manners are O(k) because we do counting until counter matching k.

Space complexity for both manners are O(h) if h denotes to the length of the longest path from root to leaves in this tree because calls in calling stack will reach up to h. Or you can say O(logn) because h is bounded by logn.

Solution — Iteration

It’s in the same idea with recursion approach but using a stack to maintain current node.

Complexity

Time complexity and space complexity are both the same with recursion approach, O(k) and O(h)(or O(logn)) correspondingly.