Finding the sum of N Biggest elements in Binary Search Tree

Trees look kind of complicated when you get started with them. But they are really fun when you are a master of recursion concepts. In today's problem we are given a binary search tree and a number N. We have to find the sum of the N biggest elements in the BST, given N <= number of elements in the BST.

Sample IO



Solution Approach

This problem can be solved using recursion. Binary Search Tree, for those of you who are not aware of, is a tree in which the elements in the right child of every node is always bigger than the node itself and every element in the left child of any node is always smaller than the node itself. So basically while solving this sum we have to just make sure that there is no element to the right of the current node and add it until the number of elements we've added reaches N. The algorithm is given below.

Let,
result be the name of the variable storing the value of the sum
sum be the name of the function
k be the number of elements added already
N be the number given in the question

1. If the right child of a node is null,

  • Increment k
  • If the left child is not null, return current_node_value + sum(node.leftChild) 
  • If the left child is null, return current_node_value
2. If the right child of a node is not null,
  • result = result + sum(node.rightChild)
  • If k != N, add the value of current node to result and increment k.
  • If k = N, return result.
3. If the left child of a node is not null,
  • result = result + sum(node.rightChild)
  • If k = N, return result.
Consider the following structure for the program.



Program


Feel free to post your doubts below :)

Comments

Popular posts from this blog

Finding the Longest Palindrome in a String

Finding a Single Number amongst Repeated Numbers [Repeated Twice]

Finding the Longest Path From One Point To Another - Dynamic Programming