CODEWITHSUNDEEP
pythonbinary-tree
fin1010
fin1010

Reputation: 69

Height of a Binary Tree - iterative

This always make only one out while loop:

def height(self):
    if self.root is None:
        return 0
    height = -1
    q = self.Queue()
    q.enqueue(self.root)
    while not q.is_empty():
        size = self.__len__()
        height += 1
        while size > 0:
            node = q.dequeue()
            if node.left is not None:
                q.enqueue(node.left)
            if node.right is not None:
                q.enqueue(node.right)
            size -= 1
    return height

Do you have any other idea (or idea how to change this code) in order to return the correct height of a binary tree?

len is number of all nodes in a tree, self.Queue is a subclass of class with method height.

Upvotes: 1

Views: 379

Answers (1)

user202729
user202729

Reputation: 3955

The problem is that in the part of the code

size = self.__len__()
while size > 0:
    # [...]
    size -= 1

the number of times the loop body is executed is equal to the number of nodes in the whole tree, which is not what you want.

Instead you want

size = len(q)

Upvotes: -1

Related Questions