Solution For Kth Smallest Element In A Bst
Problem Statement:
Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.
Example 1:
Input: root = [3,1,4,null,2], k = 1
Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Constraints:
The number of nodes in the tree is n.
1 <= k <= n <= 104
0 <= Node.val <= 104
Solution:
Approach 1: Inorder Traversal of BST
One of the simplest and most intuitive solutions for this problem is to traverse the tree in an inorder fashion. In an inorder traversal of BST, the elements are sorted in ascending order. So, we can traverse the tree in inorder, and maintain a count of the number of nodes that we have visited so far. Once the count becomes equal to k, we have reached the kth smallest element.
Algorithm:
- Traverse the BST in inorder fashion.
- While traversing, do the following:
a. When we visit a node, increment the counter by 1.
b. If the counter becomes equal to k, return the value of the current node. - If we have traversed the entire tree and haven’t found the kth smallest element, return -1.
Time Complexity:
O(n) – We have to traverse the entire tree.
Space Complexity:
O(h) – We are making use of the call stack, which can grow up to h levels, where h is the height of the tree.
Approach 2: Finding the kth Smallest Element Using Binary Search
Another approach to solve this problem is to make use of binary search. We can perform a binary search on the range of values that are present in the BST. We can start with the smallest value in the BST and the largest value in the BST, and find the middle element. We can then find the number of nodes that are smaller than or equal to this middle element. If this number is less than k, we can discard the left half of the range, and repeat the same process on the right half. If this number is greater than or equal to k, we can discard the right half of the range, and repeat the same process on the left half. We can continue performing the binary search until we find the kth smallest element.
Algorithm:
- Initialize l and r to the minimum and maximum values in the BST, respectively.
- While l <= r, do the following:
a. Set mid to (l+r)/2.
b. Set cnt to the number of nodes that are smaller than or equal to mid.
c. If cnt < k, set l to mid+1.
d. If cnt >= k, set r to mid-1. - Return l.
Time Complexity:
O(n*log(max_value-min_value)) – We have to perform binary search, which has a time complexity of O(log(max_value-min_value)), where max_value and min_value are the maximum and minimum values in the BST, respectively. We also have to find the number of nodes that are smaller than or equal to a given value, which can be done in O(n) time.
Space Complexity:
O(h) – We are making use of the call stack, which can grow up to h levels, where h is the height of the tree.
Step by Step Implementation For Kth Smallest Element In A Bst
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int kthSmallest(TreeNode root, int k) { //inorder traversal of a BST gives us the elements in sorted order Listlist = new ArrayList<>(); inorder(root, list); return list.get(k-1); } public void inorder(TreeNode root, List list){ if(root == null) return; inorder(root.left, list); list.add(root.val); inorder(root.right, list); } }
def kthSmallest(self, root: TreeNode, k: int) -> int: # Initialize an empty stack stack = [] # Push the root node to the stack stack.append(root) # Initialize a count variable to keep track of nodes visited count = 0 # Loop until stack is empty while stack: # Pop the top node from the stack node = stack.pop() # If the node has a right child, push it to the stack if node.right: stack.append(node.right) # If the node doesn't have a left child, it is a leaf node # so increment the count and check if it is the kth smallest node if not node.left: count += 1 if count == k: return node.val # If the node has a left child, push it to the stack if node.left: stack.append(node.left)
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} k * @return {number} */ var kthSmallest = function(root, k) { // create an empty array to store all node values const nums = []; // traverse the tree using in-order traversal // this will store the node values in ascending order inOrder(root); // return the kth element in the array return nums[k - 1]; function inOrder(node) { // if the node is null, return if (!node) return; // recursively call inOrder on the left child inOrder(node.left); // push the node's value into the array nums.push(node.val); // recursively call inOrder on the right child inOrder(node.right); } };
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int kthSmallest(TreeNode* root, int k) { int count = 0; int result = 0; inorder(root, k, count, result); return result; } void inorder(TreeNode* root, int k, int& count, int& result) { if (root == nullptr) { return; } inorder(root->left, k, count, result); count++; if (count == k) { result = root->val; return; } inorder(root->right, k, count, result); } };
public int KthSmallest(TreeNode root, int k) { // Base Case if (root == null) { return 0; } // Create a stack to do iterative inorder traversal Stackst = new Stack (); // Initialize current node as root TreeNode curr = root; // Traverse the tree while (curr != null || st.Count > 0) { /* Reach the left most TreeNode of the curr TreeNode */ while (curr != null) { st.Push(curr); curr = curr.left; } /* Current must be NULL at this point */ curr = st.Pop(); // Decrement count by 1 k--; // If the count becomes zero, return current if (k == 0) { return curr.val; } /* Else go to the right subtree */ curr = curr.right; } // If k is still greater than 0, then it is not // possible to find kth smallest element return -1; }