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?
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
self.root==None with self.root is None.None this way.
I am not sure of how you define your binary tree. But on a tree node you usually have only one root and multiple sons. I have the feeling that this method leads to an infinite loop. self.root.left and self.root.right are exactly my brother and me...
Here you probably have to call the method from the instances self.root.left and self.root.right with no extra argument :
def height(self):
if self.root==None:
return 0
return max(self.root.left.height(), self.root.right.height())+1
