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)