# Kth Smallest Element in a BST
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/kth-smallest-element-in-a-bst)
Canonical: https://scaleengineer.com/dsa/problems/kth-smallest-element-in-a-bst
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [Cisco](https://scaleengineer.com/companies/cisco), [Google](https://scaleengineer.com/companies/google), [Oracle](https://scaleengineer.com/companies/oracle)
---
## Problem
Given the `root` of a binary search tree, and an integer `k`, return _the_ `kth` _smallest value (**1-indexed**) of all the values of the nodes in the tree_.

**Example 1:**

![](https://assets.glich.co/dsa/kth-smallest-element-in-a-bst/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/kth-smallest-element-in-a-bst/image1.jpg) 

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

**Constraints:**

* The number of nodes in the tree is `n`.
* `1 <= k <= n <= 104`
* `0 <= Node.val <= 104`

**Follow up:** If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

# Approaches
## Inorder Traversal with Array
This approach uses inorder traversal to store all elements in an array and then returns the kth element.
**Time:** O(n) where n is the number of nodes in the tree · **Space:** O(n) to store all elements in the array
**Pros:** Simple to implement; Easy to understand; Can be used when k is not known beforehand
**Cons:** Uses extra space to store all elements; Processes all nodes even when k is small; Not efficient for large trees when k is small
### Explanation
In this approach, we perform an inorder traversal of the BST and store all elements in an array. Since inorder traversal of a BST visits nodes in ascending order, we can simply return the (k-1)th element from the array.

```java
class Solution {
    List<Integer> inorderList = new ArrayList<>();
    
    public int kthSmallest(TreeNode root, int k) {
        inorderTraversal(root);
        return inorderList.get(k-1);
    }
    
    private void inorderTraversal(TreeNode node) {
        if (node == null) return;
        
        inorderTraversal(node.left);
        inorderList.add(node.val);
        inorderTraversal(node.right);
    }
}
```
### Algorithm
1. Create a list to store elements
2. Perform inorder traversal:
   - Recursively traverse left subtree
   - Add current node value to list
   - Recursively traverse right subtree
3. Return the (k-1)th element from the list

## Iterative Inorder with Early Stopping
This approach uses iterative inorder traversal with a counter to stop when kth element is found.
**Time:** O(H + k) where H is the height of tree · **Space:** O(H) where H is the height of tree
**Pros:** More efficient than storing all elements; Stops as soon as kth element is found; Uses less memory than storing all elements
**Cons:** More complex implementation than recursive approach; Still requires stack space
### Explanation
We perform an iterative inorder traversal using a stack. We maintain a counter and stop as soon as we find the kth element, avoiding unnecessary traversal of remaining nodes.

```java
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        int count = 0;
        
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            
            curr = stack.pop();
            count++;
            
            if (count == k) {
                return curr.val;
            }
            
            curr = curr.right;
        }
        return -1;
    }
}
```
### Algorithm
1. Initialize a stack and current pointer to root
2. While current is not null or stack is not empty:
   - Push all left nodes to stack
   - Pop node from stack
   - Increment counter
   - If counter equals k, return node value
   - Move to right child

## Follow-up: Augmented BST Node
For the follow-up question where BST is modified frequently, we can augment the BST node with count of left subtree nodes.
**Time:** O(H) where H is the height of tree · **Space:** O(1) for queries (O(n) for maintaining counts in nodes)
**Pros:** O(H) time complexity for queries; Efficient for frequent queries; No extra space needed during query; Optimal for dynamic BST with frequent kth smallest queries
**Cons:** Requires modification to tree structure; Need to maintain leftCount during insertions and deletions; More complex implementation for tree modifications
### Explanation
We modify the TreeNode class to include a count of nodes in the left subtree. This helps in determining the position of current node quickly.

```java
class TreeNode {
    int val;
    int leftCount;  // count of nodes in left subtree
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
        this.leftCount = 0;
    }
}

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        TreeNode curr = root;
        
        while (curr != null) {
            if (curr.leftCount + 1 == k) {
                return curr.val;
            } else if (curr.leftCount >= k) {
                curr = curr.left;
            } else {
                k = k - (curr.leftCount + 1);
                curr = curr.right;
            }
        }
        return -1;
    }
}
```
### Algorithm
1. Augment TreeNode with leftCount
2. While traversing:
   - If leftCount + 1 equals k, return current value
   - If leftCount >= k, go left
   - Otherwise, subtract leftCount + 1 from k and go right

# Solutions
### Java

```java
import java.util.Comparator ; import java.util.PriorityQueue ; public class Kth_Smallest_Element_in_a_BST { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { PriorityQueue < Integer > heap = new PriorityQueue <>( new Comparator < Integer >() { @Override public int compare ( Integer o1 , Integer o2 ) { return o2 - o1 ; } }); public int kthSmallest ( TreeNode root , int k ) { dfs ( root , k ); return heap . peek (); } private void dfs ( TreeNode root , int k ) { if ( root == null ) { return ; } // maintain heap if ( heap . size () < k ) { heap . offer ( root . val ); // followup question, heap.remove() is by object, not index. // so if delete operation, just remove element from both tree and heap } else { int val = root . val ; if ( val < heap . peek ()) { heap . poll (); heap . offer ( val ); } } dfs ( root . left , k ); dfs ( root . right , k ); } } } class Solution_followUp { public int kthSmallest ( TreeNode root , int k ) { MyTreeNode node = build ( root ); return dfs ( node , k ); } class MyTreeNode { int val ; int count ; // key point to add up and find k-th element MyTreeNode left ; MyTreeNode right ; MyTreeNode ( int x ) { this . val = x ; this . count = 1 ; } }; MyTreeNode build ( TreeNode root ) { if ( root == null ) return null ; MyTreeNode node = new MyTreeNode ( root . val ); node . left = build ( root . left ); node . right = build ( root . right ); if ( node . left != null ) node . count += node . left . count ; if ( node . right != null ) node . count += node . right . count ; return node ; } int dfs ( MyTreeNode node , int k ) { if ( node . left != null ) { int cnt = node . left . count ; if ( k <= cnt ) { return dfs ( node . left , k ); } else if ( k > cnt + 1 ) { return dfs ( node . right , k - 1 - cnt ); // -1 is to exclude current root } else { // k == cnt + 1 return node . val ; } } else { if ( k == 1 ) return node . val ; return dfs ( node . right , k - 1 ); } } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int kthSmallest ( TreeNode root , int k ) { Deque < TreeNode > stk = new ArrayDeque <>(); while ( root != null || ! stk . isEmpty ()) { if ( root != null ) { stk . push ( root ); root = root . left ; } else { root = stk . pop (); if (-- k == 0 ) { return root . val ; } root = root . right ; } } return 0 ; } }
```

### Python

```python
# 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 : Optional [ TreeNode ], k : int ) -> int : stk = [] while root or stk : if root : stk . append ( root ) root = root . left else : root = stk . pop () k -= 1 if k == 0 : return root . val root = root . right ############ # 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_followUp : def kthSmallest ( self , root : TreeNode , k : int ) -> int : node = self . build ( root ) return self . dfs ( node , k ) class MyTreeNode : def __init__ ( self , x ): self . val = x self . count = 1 # default 1 self . left = None self . right = None def build ( self , root : TreeNode ) -> MyTreeNode : if not root : return None node = self . MyTreeNode ( root . val ) # default count already is 1 node . left = self . build ( root . left ) node . right = self . build ( root . right ) if node . left : node . count += node . left . count if node . right : node . count += node . right . count return node def dfs ( self , node : MyTreeNode , k : int ) -> int : if node . left : cnt = node . left . count if k < cnt + 1 : return self . dfs ( node . left , k ) elif k > cnt + 1 : return self . dfs ( node . right , k - 1 - cnt ) else : # k == cnt+1 return node . val else : if k == 1 : # cannot move to beginning of dfs() return node . val return self . dfs ( node . right , k - 1 )
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/kth-smallest-element-in-a-bst/ // Time: O(N) // Space: O(H) class Solution { public: int kthSmallest ( TreeNode * root , int k ) { function < int ( TreeNode * ) > inorder = [ & ]( TreeNode * root ) { if ( ! root ) return - 1 ; int val = inorder ( root -> left ); if ( val != - 1 ) return val ; if ( -- k == 0 ) return root -> val ; return inorder ( root -> right ); }; return inorder ( root ); } };
```