Python program to find height of a tree without using recursion.
Description:
Here the main idea is traverse level by level. Whenever move down to a level increment height by 1 , count number of nodes at each level, stop traversing when count of nodes at next level is 0.
Program:
import queue
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def getData(self):
return self.data
def getLeft(self):
return self.left
def getRight(self):
return self.right
def insertLeft(self, newnode):
if self.left == None:
self.left = newnode
else:
newnode.left = self.left
self.left = newnode
def insertRight(self, newnode):
if self.right == None:
self.right = newnode
else:
newnode.right = self.right
self.right = newnode
def maxHeight(root):
if root is None:
return 0
q = []
q.append(root)
height = 0
while(True):
nodeCount = len(q)
if nodeCount == 0 :
return height
height += 1
while(nodeCount > 0):
node = q[0]
q.pop(0)
if node.left is not None:
q.append(node.left)
if node.right is not None:
q.append(node.right)
nodeCount -= 1
A = BinaryTreeNode(90)
B = BinaryTreeNode(80)
C = BinaryTreeNode(30)
D = BinaryTreeNode(20)
E= BinaryTreeNode(10)
F = BinaryTreeNode(230)
G = BinaryTreeNode(45)
A.insertLeft(B)
A.insertRight(C)
B.insertLeft(D)
B.insertRight(E)
C.insertLeft(F)
C.insertRight(G)
print("Height of tree is :",maxHeight(A))
Output:
Height of tree is : 3
>>>
Comments