Given a Binary Search Tree. Find sum of all elements smaller than and equal to Kth smallest element.
Example 1:
Input: 
          20
        /    \
       8     22
     /    \
    4     12
         /    \
        10    14   , K=3
Output: 22
Explanation:
Sum of 3 smallest elements are: 
4 + 8 + 10 = 22
Example 2:
Input:
     10
    /  \
   5    11
  / \ 
 4   7
      \
       8 , K=2
Output: 9
Explanation:
The sum of two smallest elements 
is 4+5=9.
 
Your task:
You don't need to read input or print anything. Your task is to complete the function sum() which takes the root node and an integer K as input parameters and returns the sum of all elements smaller than and equal to kth smallest element.
 
Expected Time Complexity: O(K)
Expected Auxiliary Space: O(1)
 
Constraints:
1<=Number of nodes in BST<=100
1<=K<=N

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Range queries

Starter code: #User function Template for python3



'''

# Node Class:

class Node:

    def __init__(self,val):

        self.key = val

        self.left = None

        self.right = None

'''



def summ(root, k):

    # code here

Solutions:
def summ(root, k):
	s = [0]
	l = [0]

	def find(root, l):
		if root == None:
			return
		if l[0] > k:
			return
		find(root.left, l)
		if l[0] < k:
			s[0] += root.key
		l[0] += 1
		find(root.right, l)
	find(root, l)
	return s[0]


def summ(root, k):

	def inOrderTraversal(root):
		result = []
		if root.left is not None:
			result = inOrderTraversal(root.left)
		result.append(root.key)
		if root.right is not None:
			result.extend(inOrderTraversal(root.right))
		return result
	order = inOrderTraversal(root)
	sum = 0
	for i in range(k):
		sum += order[i]
	return sum


def inorder(root):
	return [] if not root else inorder(root.left) + [root.key] + inorder(root.right)

def summ(root, k):
	return sum(inorder(root)[:k])


def inorder(node, a):
	if node is None:
		return
	inorder(node.left, a)
	a.append(node.key)
	inorder(node.right, a)
	return a

def summ(root, k):
	li = inorder(root, [])
	li = li[:k]
	return sum(li)


def summ(root, k):
	a = []

	def inorder(root):
		if root != None:
			inorder(root.left)
			a.append(root.key)
			inorder(root.right)
	inorder(root)
	ans = sum(a[:k])
	return ans


def trav(root, li):
	if not root:
		return
	trav(root.left, li)
	li.append(root.key)
	trav(root.right, li)

def summ(root, k):
	li = []
	trav(root, li)
	return sum(li[:k])


def summ(root, k):
	a = []

	def ino(root):
		if root:
			ino(root.left)
			a.append(root.key)
			ino(root.right)
	ino(root)
	return sum(a[:k])


def summ(root, k):
	return recursive_sum(root, k)[0]

def recursive_sum(root, k):
	sum = 0
	n = k
	if root.left is not None:
		(sum_left, n) = recursive_sum(root.left, n)
		sum += sum_left
	if n > 0:
		n -= 1
		sum += root.key
	if n > 0 and root.right is not None:
		(sum_right, n) = recursive_sum(root.right, n)
		sum += sum_right
	return (sum, n)


def Inorder(root, sum_, count, k):
	if root == None:
		return None
	Inorder(root.left, sum_, count, k)
	if count[0] == k:
		return None
	sum_[0] += root.key
	count[0] += 1
	Inorder(root.right, sum_, count, k)

def summ(root, k):
	sum_ = [0]
	count = [0]
	Inorder(root, sum_, count, k)
	return sum_[0]


def summ(root, k):
	re = []

	def trav(r):
		re.append(r.key)
		if r.left is not None:
			trav(r.left)
		if r.right is not None:
			trav(r.right)
	trav(root)
	a = 0
	re = sorted(re)
	for i in range(k):
		a += re[i]
	return a


def summ(root, k):
	b = []
	bst(root, b)
	b.sort()
	if k < len(b):
		return sum(b[0:k])
	return sum(b)

def bst(root, b):
	if root.left:
		bst(root.left, b)
	b.append(root.key)
	if root.right:
		bst(root.right, b)


def solve(root, k, cnt, sm):
	if root is not None:
		solve(root.left, k, cnt + 1, sm)
		sm.append(root.key)
		solve(root.right, k, cnt + 1, sm)

def summ(root, k):
	cnt = 0
	sm = []
	solve(root, k, cnt, sm)
	return sum(sm[0:k])


import heapq

def find(root, k, arr):
	if root is None:
		return
	find(root.left, k, arr)
	arr.append(root.key)
	find(root.right, k, arr)

def summ(root, k):
	arr = []
	find(root, k, arr)
	arr = heapq.nsmallest(k, arr)
	return sum(arr)


def summ(root, k):
	count = 0
	ans = 0

	def sol(node, k):
		nonlocal count, ans
		if node is None:
			return
		sol(node.left, k)
		count += 1
		if count <= k:
			ans += node.key
		else:
			return
		sol(node.right, k)
	sol(root, k)
	return ans


fg = 0
tot = 0
k = 0

def calcSum(root):
	global fg, tot, k
	if root == None:
		return
	calcSum(root.left)
	if fg < k:
		fg += 1
		tot += root.key
	calcSum(root.right)

def summ(root, num):
	global fg, tot, k
	fg = 0
	tot = 0
	k = num
	calcSum(root)
	return tot


def summ(root, k):
	s = []

	def inorder(root):
		if root != None:
			inorder(root.left)
			s.append(root.key)
			inorder(root.right)
	inorder(root)
	return sum(s[:k])


def summ(root, k):
	return sum(helper(root, k)[:k])

def helper(root, k):
	if root is None:
		return []
	output = helper(root.left, k)
	if len(output) < k:
		output.append(root.key)
	if len(output) < k:
		output += helper(root.right, k)
	return output


class Node:

	def __init__(self, val):
		self.key = val
		self.left = None
		self.right = None

def summ(root, k):
	count = [0]
	return ksmallestElementSumRec(root, k, count)

def ksmallestElementSumRec(root, k, count):
	if root is None:
		return 0
	res = ksmallestElementSumRec(root.left, k, count)
	if count[0] >= k:
		return res
	res += root.key
	count[0] += 1
	if count[0] >= k:
		return res
	return res + ksmallestElementSumRec(root.right, k, count)


def tra(root, k, al):
	if root == None:
		return 0
	tra(root.left, k, al)
	if len(al) < k:
		al.append(root.key)
	tra(root.right, k, al)

def summ(root, k):
	al = []
	tra(root, k, al)
	return sum(al)


def summ(root, k):
	res = []
	_summ(root, res)
	return sum(res[:k])

def _summ(root, res):
	if root:
		_summ(root.left, res)
		res.append(root.key)
		_summ(root.right, res)


def summ(root, k):
	res = []

	def inorder(node):
		if node:
			inorder(node.left)
			res.append(node.key)
			inorder(node.right)
	inorder(root)
	return sum(res[:k])


a = int(input())
for i in range(a):
	b = list(map(str, input().split()))
	s = int(input())
	e = []
	for i in b:
		if i != 'N':
			e.append(int(i))
	e.sort()
	print(sum(e[0:s]))


def summ(root, k):
	l = []
	inorder(root, l, k)
	return sum(l)

def inorder(root, l, k):
	if not root:
		return
	inorder(root.left, l, k)
	if len(l) == k:
		return l
	else:
		l.append(root.key)
	inorder(root.right, l, k)


def inorder(root, A):
	if root is None:
		return
	inorder(root.left, A)
	A.append(root.key)
	inorder(root.right, A)
	return A

def summ(root, k):
	A = inorder(root, [])
	return sum(A[0:k])


def summ(root, k):

	def getSum(root):
		nonlocal result, i
		if not root or i > k:
			return
		getSum(root.left)
		i += 1
		if i <= k:
			result += root.key
		getSum(root.right)
	i = result = 0
	getSum(root)
	return result


def inorder(root, l):
	if root == None:
		return []
	else:
		inorder(root.left, l)
		l.append(root.key)
		inorder(root.right, l)

def summ(root, k):
	l = []
	inorder(root, l)
	return sum(l[:k])


def inorder(root):
	l = []
	q = []
	cur = root
	while True:
		if cur is not None:
			q.append(cur)
			cur = cur.left
		elif q:
			cur = q.pop()
			l.append(cur.key)
			cur = cur.right
		else:
			break
	return l

def summ(root, k):
	ino = inorder(root)
	return sum(ino[:k])


def getPreorder(root, result):
	if root:
		getPreorder(root.left, result)
		result.append(root.key)
		getPreorder(root.right, result)

def summ(root, k):
	result = []
	getPreorder(root, result)
	sumk = 0
	for i in range(k):
		sumk += result[i]
	return sumk


def summ(root, k):
	sum = [0]
	d = [k]

	def dfs(root):
		if root == None:
			return
		if d[0] == 0:
			return
		dfs(root.left)
		if d[0] != 0:
			sum[0] += root.key
			d[0] -= 1
		dfs(root.right)
	dfs(root)
	return sum[0]


def summ(root, k):

	def helper(root):
		x = []
		if not root:
			return x
		x += helper(root.left)
		x.append(root.key)
		x += helper(root.right)
		return x
	a = helper(root)
	return sum(a[:k])


def summ(root, k):
	(st, res) = ([], 0)
	while True:
		while root:
			st.append(root)
			root = root.left
		if not st or not k:
			return res
		(node, k) = (st.pop(), k - 1)
		res += node.key
		root = node.right


def summ(root, k):
	n = 0
	s = 0
	(s, n) = find(root, k, s, n)
	return s

def find(root, k, s, n):
	if root is None:
		return (s, n)
	(s, n) = find(root.left, k, s, n)
	if n < k:
		s += root.key
		n += 1
		(s, n) = find(root.right, k, s, n)
	return (s, n)


class Node:

	def __init__(self, val):
		self.key = val
		self.left = None
		self.right = None

def summ(root, k):
	if root is None:
		return None
	else:
		import collections
		q = collections.deque()
		q.append(root)
		res = []
		while q:
			for i in range(len(q)):
				node = q.popleft()
				if node:
					res.append(node.key)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		res.sort()
		count = sum(res[:k])
		return count


def summ(root, k):
	stack = []
	count = 0
	summ = 0
	while stack or root:
		while root:
			stack.append(root)
			root = root.left
		root = stack.pop()
		summ += root.key
		count += 1
		if count == k:
			return summ
		root = root.right


def summ(root, k):
	curr_node = root
	stack = []
	result = 0
	while True:
		if curr_node:
			stack.append(curr_node)
			curr_node = curr_node.left
		elif stack:
			curr_node = stack.pop()
			if k > 0:
				k -= 1
				result += curr_node.key
			curr_node = curr_node.right
		else:
			break
	return result


def summ(root, k):
	stack = []
	current_node = root
	result = []
	while True:
		if current_node:
			stack.append(current_node)
			current_node = current_node.left
		elif stack:
			current_node = stack.pop()
			result.append(current_node.key)
			current_node = current_node.right
		else:
			break
	return sum(result[:k])


def summ(root, k):
	s = 0

	def funk(root, s, k):
		if k == 0 or root == None:
			return [s, k]
		b = funk(root.left, s, k)
		s = b[0]
		k = b[1]
		if k > 0:
			k -= 1
			s += root.key
		return funk(root.right, s, k)
	return funk(root, s, k)[0]


def summ(root, k):
	res = []

	def inorder(root):
		if root:
			inorder(root.left)
			res.append(root.key)
			inorder(root.right)
		return res
	inorder(root)
	ans = 0
	if res:
		ans = sum(res[:k])
	return ans


def summ(root, k):
	s = []
	c = root
	res = 0
	cc = 0
	while True:
		if c is not None:
			s.append(c)
			c = c.left
		elif s:
			c = s.pop()
			if cc == k:
				break
			res += c.key
			cc += 1
			c = c.right
		else:
			break
	return res


class data:

	def __init__(self):
		self.sum = 0
		self.K = 0
Data = data()

def summ(root, k):
	Data.K = k
	Data.sum = 0
	helper(root)
	return Data.sum

def helper(root):
	if not root or Data.K == 0:
		return
	helper(root.left)
	if Data.K:
		Data.sum += root.key
		Data.K -= 1
	helper(root.right)


def summ(root, k):
	l = []

	def preorder(rt):
		if rt.left:
			preorder(rt.left)
		l.append(rt.key)
		if rt.right:
			preorder(rt.right)
	preorder(root)
	k = sum(l[:k])
	return k


def summ(root, k):
	el = []

	def helper(root):
		if not root:
			return None
		helper(root.left)
		el.append(root.key)
		helper(root.right)
	helper(root)
	return sum(el[:k])


def summ(root, k):
	ans = 0
	k = k

	def helper(root):
		nonlocal k, ans
		if root:
			helper(root.left)
			if k > 0:
				ans += root.key
				k -= 1
			helper(root.right)
	helper(root)
	return ans


def summ(root, k):
	global count, res
	res = 0
	count = 0
	f(root, k)
	return res

def f(root, k):
	global count, res
	if root == None:
		return
	f(root.left, k)
	count += 1
	if count <= k:
		res = res + root.key
	f(root.right, k)


def summ(root, k):
	ans = 0
	stk = []
	node = root
	while len(stk) != 0 or node != None:
		if node != None:
			stk.append(node)
			node = node.left
		else:
			node = stk.pop()
			k -= 1
			ans += node.key
			if k == 0:
				return ans
			node = node.right
	return ans


def summ(root, k):
	if k == 0:
		return 0
	return summ1(root, k)

def summ1(root, k):
	if root == None or k == 0:
		return (0, k)
	output1 = summ1(root.left, k)
	if type(output1) == int:
		return output1
	elif output1[1] == 0:
		return output1[0]
	output = (output1[0] + root.key, output1[1] - 1)
	if output[1] == 0:
		return output[0]
	else:
		output2 = summ1(root.right, output[1])
		if type(output2) == int:
			return output[0] + output2
		elif output2[0] == 0:
			return output
		else:
			return (output[0] + output2[0], output2[1])


def summ(root, k):
	sum1 = [0]
	k1 = [k]
	Helper(root, k1, sum1)
	return sum1[0]

def Helper(root, k, sum1):
	if root is None:
		return
	Helper(root.left, k, sum1)
	if k[0] > 0:
		sum1[0] += root.key
		k[0] -= 1
	if k[0] > 0:
		Helper(root.right, k, sum1)


def ino(r, l):
	if r is None:
		return
	ino(r.left, l)
	l.append(r.key)
	ino(r.right, l)

def summ(root, k):
	l = []
	ino(root, l)
	return sum(l[:k])


from heapq import heapify, heappush, heappop

def summ(root, k):

	def inorder(heap, root):
		if not root:
			return
		inorder(heap, root.left)
		heappush(heap, root.key)
		inorder(heap, root.right)
	heap = []
	heapify(heap)
	inorder(heap, root)
	sum = 0
	for i in range(k):
		sum += heappop(heap)
	return sum


def summ(root, k):
	stack = inOrder(root, k, [])
	sumA = 0
	if stack is not None:
		for s in stack:
			if s is not None:
				sumA += s.key
	return sumA

def inOrder(root, k, stack):
	if root is None:
		print('NONE')
		return stack
	if root.left is not None:
		inOrder(root.left, k, stack)
	if len(stack) < k:
		if root is not None:
			stack.append(root)
	else:
		return stack
	if root.right is not None:
		inOrder(root.right, k, stack)
	return stack


def summ(root, k):
	N = [0]
	S = [0]
	ans = [0]

	def inorder(root):
		if root is None:
			return
		inorder(root.left)
		N[0] += 1
		if N[0] <= k:
			S[0] = S[0] + root.key
		inorder(root.right)
	inorder(root)
	return S[0]


def sum_recursive(root, k):
	vs = [root.key]
	if root.left is not None:
		lvs = sum_recursive(root.left, k)
		for l in lvs:
			vs.append(l)
	if root.right is not None:
		rvs = sum_recursive(root.right, k)
		for r in rvs:
			vs.append(r)
	vs.sort()
	return vs[:k]

def summ(root, k):
	vs = sum_recursive(root, k)
	return sum(vs[:k])


def ksmallestElementSumRec(root, k, count):
	if root == None:
		return 0
	if count[0] >= k:
		return 0
	res = ksmallestElementSumRec(root.left, k, count)
	if count[0] >= k:
		return res
	res += root.key
	count[0] += 1
	if count[0] >= k:
		return res
	return res + ksmallestElementSumRec(root.right, k, count)

def summ(root, k):
	count = [0]
	return ksmallestElementSumRec(root, k, count)


class Solution:

	def inorder(self, root):
		if root is None:
			self.flag = True
			return
		self.inorder(root.left)
		if self.flag:
			self.k -= 1
		if self.flag and self.k >= 0:
			self.total += root.key
		self.inorder(root.right)

	def sumSmaller(self, root, k):
		self.flag = False
		self.total = 0
		self.k = k
		self.inorder(root)
		return self.total

def summ(root, k):
	return Solution().sumSmaller(root, k)


def summ(root, k):

	def addval(r, s, e, k):
		(ns, ne) = (s, e)
		if r.left:
			(ns, ne) = addval(r.left, s, e, k)
		if ne < k:
			ns += r.key
			ne += 1
		if ne < k and r.right:
			(ns, ne) = addval(r.right, ns, ne, k)
		return (ns, ne)
	return addval(root, 0, 0, k)[0]


def dfs(root, k, i, s):
	if root == None or i[0] == k:
		return
	dfs(root.left, k, i, s)
	if i[0] == k:
		return
	s[0] = s[0] + root.key
	i[0] += 1
	dfs(root.right, k, i, s)

def summ(root, k):
	s = [0]
	i = [0]
	dfs(root, k, i, s)
	return s[0]


def summ(root, k):
	ans = 0

	def inOrder(root):
		nonlocal k, ans
		if not root:
			return
		inOrder(root.left)
		if k > 0:
			ans += root.key
			k -= 1
		else:
			return ans
		inOrder(root.right)
	inOrder(root)
	return ans


def order(root, s):
	if not root:
		return
	order(root.left, s)
	s.append(root.key)
	order(root.right, s)

def summ(root, k):
	s = []
	order(root, s)
	return sum(s[:k])


def levelorder(root):
	l = []
	if root is None:
		return l
	queue = []
	queue.append(root)
	while len(queue) != 0:
		p = queue.pop(0)
		l.append(p.key)
		if p.left:
			queue.append(p.left)
		if p.right:
			queue.append(p.right)
	return l

def summ(root, k):
	arr = levelorder(root)
	arr.sort()
	return sum(arr[:k])


def summ(root, k):

	def summ_rec(root, k, counter_in=0):
		if counter_in == k or root is None:
			return (counter_in, 0)
		(counter_out, res_left) = summ_rec(root.left, k, counter_in)
		if counter_out == k:
			return (counter_out, res_left)
		else:
			(counter_out, res_right) = summ_rec(root.right, k, counter_out + 1)
			return (counter_out, res_left + root.key + res_right)
	(_, result) = summ_rec(root, k)
	return result


def summ(root, k):
	arr = []

	def inorder(root):
		if root:
			inorder(root.left)
			arr.append(root.key)
			inorder(root.right)
		return arr
	inorder(root)
	ans = 0
	for i in range(0, k):
		ans += arr[i]
	return ans


def sol(root, ans, k):
	if k[0] > 0 and root.left != None:
		sol(root.left, ans, k)
	if k[0] > 0:
		ans[0] += root.key
		k[0] -= 1
	if k[0] > 0 and root.right != None:
		sol(root.right, ans, k)

def summ(root, k):
	ans = [0]
	k = [k]
	sol(root, ans, k)
	return ans[0]


def summ(root, k):
	elems = traverse(root, k)
	return sum(elems)

def traverse(node, k, result=None):
	if result is None:
		result = []
	if len(result) >= k:
		return result
	if node.left:
		traverse(node.left, k, result)
	if len(result) < k:
		result.append(node.key)
	if len(result) < k and node.right:
		traverse(node.right, k, result)
	return result


def summ(root, k):
	sum = 0

	def calc(root, k, sum):
		if not root or k == 0:
			return [sum, k]
		b = calc(root.left, k, sum)
		sum = b[0]
		k = b[1]
		if k > 0:
			sum += root.key
			k = k - 1
		return calc(root.right, k, sum)
	return calc(root, k, 0)[0]


def summ(root, k):
	ans = []

	def dfs(root):
		if root:
			ans.append(root.key)
			dfs(root.left)
			dfs(root.right)
	dfs(root)
	ans.sort()
	return sum(ans[:k])


def summ(root, k):
	result = []

	def inorder(root):
		if root:
			inorder(root.left)
			result.append(root.key)
			inorder(root.right)
		return result
	inorder(root)
	total = 0
	if result:
		total = sum(result[:k])
	return total


def solve(root, k):
	ans = 0
	if root.left:
		(x, k) = solve(root.left, k)
		ans += x
	if k > 0:
		ans += root.key
		k -= 1
	if k > 0 and root.right:
		(x, k) = solve(root.right, k)
		ans += x
	return (ans, k)

def summ(root, k):
	(ans, _) = solve(root, k)
	return ans


def summ(root, k):
	count = [0]
	total = [0]

	def rec(node):
		if not node:
			return
		rec(node.left)
		if count[0] == k:
			return
		count[0] += 1
		total[0] += node.key
		rec(node.right)
	rec(root)
	return total[0]


def summ(root, k):
	a = []
	a.append(root)
	f = []
	while len(a) > 0:
		x = a.pop(0)
		f.append(x.key)
		if x.left != None:
			a.append(x.left)
		if x.right != None:
			a.append(x.right)
	f.sort()
	y = f[0:k]
	return sum(y)