CODEWITHSUNDEEP
pythonpython-3.x
Lozansky
Lozansky

Reputation: 374

Height of binary tree

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?

Upvotes: 5

Views: 4705

Answers (2)

Eli Korvigo
Eli Korvigo

Reputation: 10493

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

Upvotes: 8

Vince
Vince

Reputation: 336

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

Upvotes: 0

Related Questions