Binary tree height

Question

I am 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 a function, I get the following msg error:

 NameError: name 'height' is not defined 

Does anyone see a problem?

Answer 1

This is the method of your class, so you must call it from an instance ( self ) or the class itself. Although it will not work, what do you think, unless you define it as a staticmethod or change your call, for example

 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) 

Note that you should not use == to compare with None (kudos to timgeb). And you have to check if child nodes exist. And your algorithm does not work, so I changed it a bit.

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 

Answer 2

I'm not sure how you define your binary tree. But on a node tree, you usually only have one root and several sons. I have the feeling that this method leads to an infinite loop. self.root.left and self.root.right are my brother and I ...

Here you will probably have to call the method from instances of self.root.left and self.root.right without additional arguments:

 def height(self): if self.root==None: return 0 return max(self.root.left.height(), self.root.right.height())+1