Height of Binary Tree?

Question

I'm trying to implement a recursive method to calculate the height of a binary tree. Here is the "height"-code:

def HeightOfTree(self):
    if self.root is None:
        return 0
    else:
        ans=self._HeightOfTree(self.root)
        return ans

def _HeightOfTree(self,currentNode):
    if currentNode.hasleftChild():
        lheight=1+self._HeightOfTree(currentNode.leftChild)
    if currentNode.hasrightChild():
        rheight=1+self._HeightOfTree(currentNode.rightChild)
    if lheight > rheight:
        return (lheight+1)
    else:
        return (rheight+1)

When I try to call the function, I get the following error msg:

UnboundLocalError: local variable 'lheight' referenced before assignment

How can I fix this problem ?

What is your tree is a single node? Neither `lheight` or `rheight` will have a value. — Patrick Haugh, Jul 25 '18 at 17:34
A side note: you need to have a base case whenever you use recursion. Otherwise, the function will never end (or it will break down). — Ben Jones, Jul 25 '18 at 17:37

score 3 · Answer 1 · answered Jul 25 '18 at 17:31

If you're setting the value of a variable in an if block and you try to use it later, make sure that it's declared before the block so that if the if doesn't happen, it still exists.

Wrong:

if False:
    x = 3
print(x)
# UnboundLocalError

Right:

x = 0
if False:
    x = 3
print(x)
# 0

score 0 · Answer 2 · answered Jul 25 '18 at 17:56

You are getting the UnboundLocalError because the values rheight and lheight are not created in the case that leftChild or rightChild are None.

It would be simpler if you defined a base case of _HeightOfTree(None) == 0:

def _HeightOfTree(self,currentNode):
    if currentNode is None:
        return 0
    return 1 + max(self._HeightOfTree(currentNode.leftChild), self._HeightOfTree(currentNode.rightChild))

Height of Binary Tree?

2 Answers2