Sum of k smallest elements in BST
Given Binary Search Tree. The task is to find sum of all elements smaller than and equal to Kth smallest element.
Examples:
Input : K = 3
8
/ \
7 10
/ / \
2 9 13
Output : 17
Explanation : Kth smallest element is 8 so sum of all
element smaller then or equal to 8 are
2 + 7 + 8
Input : K = 5
8
/ \
5 11
/ \
2 7
\
3
Output : 25
class Solution {
int count = 0;
int sum = 0;
public int kthSmallest(TreeNode root, int k) {
traverse(root, k);
return sum;
}
public void traverse(TreeNode root, int k) {
if (root == null)
return;
traverse(root.left, k);
count++;
if (count <= k)
sum += root.val;
if (count < k)
traverse(root.right, k);
}
}
PreviousConstruct a special tree from given preorder traversalNextCheck whether BST contains Dead End or not
Last updated