## DEV Community is a community of 550,319 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 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

1. initialize empty array
2. loop through the root and push root to stack and change root to root.left
3. Now we have all left nodes
4. take the last node
5. Decrement k by 1. if it's 0 return node value
6. 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
}
}
``````

## Discussion 