Search code examples
pythonalgorithmtreesegment-tree

Do I need to check if lo > hi when building a segment tree


The code below is a slightly modified version of popular segment tree code.

My question is why do we need to do the lo > hi check when recursively building the tree, I cannot think of an example where lo will ever be greater than hi since at any point they are equal [2,2] the recursion will not go any deeper.

class SegmentNode:

  def __init__(self, start, end):

    self.value = 0
    self.start = start
    self.end = end
    self.left = None
    self.right = None

class SegmentTree:

  def __init__(self, nums):

    self.root = self.buildTree(nums, 0, len(nums)-1)


  def buildTree(self, nums, lo, hi):

    if lo > hi:
      return None

    if lo == hi:
      curr = SegmentNode(lo, hi)
      curr.value = nums[lo]
      return curr

    mid = (lo + hi)//2

    curr = SegmentNode(lo, hi)
    curr.left = buildTree(lo, mid)
    curr.right = buildTree(mid+1, hi)

    curr.value = curr.left.value + curr.right.value

    return curr

Solution

  • I cannot think of an example where lo will ever be greater than hi

      def __init__(self, nums):
    
        self.root = self.buildTree(nums, 0, len(nums)-1)
    
    
      def buildTree(self, nums, lo, hi):
    
        if lo > hi:
          return None
    

    One example is:

    If an empty list is passed as nums to __init__, then buildTree is called with 0 as lo and -1 as hi.