CODEWITHSUNDEEP
algorithmbinary-search-tree
Amir Hossein F
Amir Hossein F

Reputation: 420

Find the sum of nodes in a binary search tree whose value lie in a certain range by augmenting the BST

I want to augment a binary search tree such that search, insertion and delete be still supported in O(h) time and then I want to implement an algorithm to find the sum of all node values in a given range.

Upvotes: 1

Views: 1656

Answers (1)

Marquis Blount
Marquis Blount

Reputation: 8115

If you add an additional data structure to your BST class, specifically a Hashmap or Hashtable. Your keys will be the different numbers your BST contains and your values the number of occurrences for each. BST search(...) will not be impacted however insert(...) and delete(...) will need slight code changes.

Insert

When adding nodes to the BST check to see if that value exist in the Hashmap as a key. If it does exist increment occurrence count by 1. If it doesn't exist add it to the Hashmap with an initial value of 1.

Delete

When deleting decrement the occurrence count in the Hashmap (assuming your aren't being told to delete a node that doesn't exist)

Sum

Now for the sum function 

sum(int start, int end)

You can iteratively check your Hashmap to see which numbers from the range exist in your map and their number of occurrences. Using this you can build out your sum by adding up all of the values in the Map that are in the range multiplied by their number of occurrences.

Complexities

Space: O(n) Time of sum method: O(range size).
All other method time complexity isn't impacted.

You didn't mention a space restraint so hopefully this is OK. I am very interested to see if you can some how use the properties of a BST to solve this more efficiently nothing comes to mind for me.

Upvotes: 2

Related Questions