Count entries in an interval

Given a BST where each node is augmented with number of nodes under it, how would you find the number of nodes in a given interval

Solution

  • Find the leftmost node that is closest to the start_interval,
  • Compare the value and go left or right, if we fall off the tree at any point we should stop as thats the closest we can get to the value
  • While doing this each time we take the left child we leave the count unchanged, when we take the right child we add 1 + left children to the count
  • Similarly find the right most node that is closest to the end_interval
  • Now subtract this from the total number of nodes at the root to get the number of entries that are within the specified interval

Complexity

  • Since we are essentially descending down the height of the tree in both cases, the overall complexity is O(log n)

results matching ""

    No results matching ""