## DEV Community

Subramanya Chakravarthy

Posted on

# 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
}
}
``````

DEV Community

## Advice For Junior Developers

Advice from a career of 15+ years for new and beginner developers just getting started on their journey.