How To Find Kth Smallest Element In A Binary Search Tree (BST) | Javascript Solution
Kth Smallest Element In A BST is an example of null problems. In this post we will see how we can solve in Javascript.
Problem Description
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Example 1
Input: root = [3,1,4,null,2], k = 1
3 / \ 1 4 \ 2
Output: 1
Example 2
Input: root = [5,3,6,2,4,null,null,1], k = 3
5 / \ 3 6 / \ 2 4 / 1
Output: 3
Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How * would you optimize the kthSmallest routine?
Solution: Please check the main.js snippet for the solution. If you have different approach in mind or have any suggestion for this implementation feel free to share in the comment below. Thanks!
Comments
Leave a comment
You are not LoggedIn but you can comment as an anonymous user which requires manual approval. For better experience please Login.