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