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
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
.