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 height(self):
    if self.root==None:
        return 0
    return max(height(self.root.left), height(self.root.right))+1

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

NameError: name 'height' is not defined

Does anybody see the problem?

Answer 1

This is a method of your class, hence you must call it from an instance (self) or the class itself. Though it won't work as you think, unless you define it as a staticmethod or change your call, e.g.

def height(self):
    return 1 + max(self.left.height() if self.left is not None else 0, 
                   self.right.height() if self.right is not None else 0) 

or

@staticmethod
def height(self):
    return 1 + max(self.height(self.left) if self.left is not None else 0,
                   self.height(self.right) if self.right is not None else 0)

Notice, that you shouldn't use == to compare with None (kudos to timgeb). And you must check whether child-nodes exist, too. And your algorithm doesn't work, so I've changed it slightly.

Example:

class Node:
    def __init__(self, root=None, left=None, right=None):
        self.root = root
        self.left = left
        self.right = right

    def height(self):
        return 1 + max(self.left.height() if self.left is not None else 0, 
                       self.right.height() if self.right is not None else 0)


# Create a binary tree of height 4 using the binary-heap property
tree = [Node() for _ in range(10)]
root = tree[0]

for i in range(len(tree)):
    l_child_idx, r_child_idx = (i + 1) * 2 - 1, (i + 1) * 2
    root_idx = (i + 1) // 2
    if root_idx: 
        tree[i].root = tree[root_idx]
    if l_child_idx < len(tree):
        tree[i].left = tree[l_child_idx]
    if r_child_idx < len(tree):
        tree[i].right = tree[r_child_idx]

print(root.height())  # -> 4