#
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

Answer is 1 because the 1st smallest element when binary tree is sorted is 1

Example 2:

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

```
5
/ \
3 6
/ \
```

2 4

/

1

Answer is 3, as 1 and 2 are 1st and 2nd smallest elements in the tree and the next is 3 which is 3rd smallest element

A simple approach would be traversing the whole tree using inorder traveral and push the elements to a stack.

Now the stack will be in ascending order. All you need is stack's *k-1* th element

Here's the code

```
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function(root, k) {
let inorder = (node, arr) => {
if(!node) return arr
inorder(node.left, arr)
arr.push(node.val)
inorder(node.right, arr)
return arr
}
let sortedArr = inorder(root, [])
return sortedArr[k - 1]
};
```

The algorithm can be improved when k is considered and finding only k elements

Thee algorithm is

- initialize empty array
- loop through the root and push root to stack and change root to root.left
- Now we have all left nodes
- take the last node
- Decrement k by 1. if it's 0 return node value
- assign root = root.right

Here's the code for iteration:

```
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function(root, k) {
let stack = new Array()
while(true) {
while(root) {
stack.push(root)
root = root.left
}
root = stack.pop()
if(--k == 0) return root.val
root = root.right
}
}
```

## Top comments (0)