CODEWITHSUNDEEP
pythontree
ZpfSysn
ZpfSysn

Reputation: 889

Python: Calculate the max height of a tree with multiple children

def __init__(self,label=None):
    self.label = label
    self.leftMostChild = None
    self.RightSibling = None


def height(self):
    if self.leftMostChild == None and self.RightSibling == None:
        return 0
    else:
        if self.leftMostChild:
            return self.leftMostChild.height() + 1

        if self.RightSibling:
            return self.RightSibling.height()

Apparently, the height is off by 1. When a tree with height 3 is produced, 2 gets return after calling the function height. I am not sure where did i do wrong in this function.

Any help would be appreciated.

Upvotes: 0

Views: 495

Answers (1)

Will
Will

Reputation: 425

Return causes a function to end immediately. This means that if a node has both a left most child and a right sibling, the right sibling will never be evaluated. Here is the function with only one return for each if/else branch.

def height(self):
    if self.leftMostChild == None and self.RightSibling == None:
        return 0
    else:
        leftHeight = rightHeight = 0
        if self.leftMostChild:
            leftHeight =  self.leftMostChild.height() + 1

        if self.RightSibling:
            rightHeight = self.RightSibling.height()
        return max(leftHeight, rightHeight)

This can be further simplified to:

def height(self):
    leftHeight = rightHeight = 0
    if self.leftMostChild:
        leftHeight =  self.leftMostChild.height() + 1
    if self.RightSibling:
        rightHeight = self.RightSibling.height()
    return max(leftHeight, rightHeight)

Upvotes: 1

Related Questions