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);
    }
}

Last updated