Hi Guys! Nayan this side and welcome to 65'th day of 100DaysOfCode Challenge. I guess we are 2/3rd done in this journey as of next article. It has been the most consistent I have ever been and I am really loving coding and programming at the moment.
Let's get to today's question. We are going to solve another Binary Search Tree Question.
Question: Kth Smallest Element in a BST
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
Example 1:
Intuition:
I have already talked about Binary Search Trees in one of my previous articles but To give a one line definition again. A Binary Search tree is a binary tree which contains all elements less than the root in it's left subtree and all elements greater in it's right subtree. Every subtree should also be a BST.
So from the properties, we can safely observe that the values which are smaller will lie on the left side and greater on the right side. Which means we will first need to traverse our left subtree for answer.
One more property of a BST is that If we do the inorder traversal of a Binary Tree it will give us all it's elements in a sorted increasing order manner.
Using this property we just need to find out that kth element in the order traversal and we have got our answer.
Algorithm and Code:
Algorithm
The algorithm follows a recursive approach to traverse the binary tree and find the kth smallest element. Let's dive into the key components of the code:
-
helper
Function:
Thehelper
function is a recursive function that traverses the binary tree in an inorder fashion, effectively visiting nodes in ascending order. Here's how it works:- If the
root
node isNULL
, the function returns without any action. - The function first traverses the left subtree by calling
helper(root->left, k, result)
. - The value of
k
is decremented, effectively tracking the number of nodes visited so far. - When
k
reaches 0, theresult
is updated with the current node's value, and the function returns. - The function then traverses the right subtree by calling
helper(root->right, k, result)
.
- If the
kthSmallest
Function:
ThekthSmallest
function initializes a variableresult
to store the kth smallest element's value. It calls thehelper
function to traverse the binary tree and updateresult
whenk
becomes 0.
Complexity Analysis
- Time: O(N)
- Space: O(N)
Explanation:
- The time complexity of the algorithm is determined by the height of the binary tree. In the worst case, when the tree is unbalanced, the time complexity is O(N), where N is the number of nodes in the tree.
- The space complexity is O(H), where H is the height of the binary tree, due to the recursive stack used for traversing.
Code:
void helper(TreeNode* root, int& k, int& result) {
if (root == NULL)
return;
helper(root->left, k, result);
k--;
if (k == 0) {
result = root->val;
return;
}
helper(root->right, k, result);
}
int kthSmallest(TreeNode* root, int k) {
int result = -1; // Initialize result to a default value
helper(root, k, result);
return result;
}
Thanks for reading!. Feel free to leave back constructive criticism.
Top comments (0)