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
classBinaryTreeNode:def__init__(self, data):
self.data = data
self.left = None
self.right = NonedefgetData(self):return self.data
defgetLeft(self):return self.left
defgetRight(self):return self.right
definsertLeft(self, newnode):if self.left == None:
self.left = newnode
else:
newnode.left = self.left
self.left = newnode
definsertRight(self, newnode):if self.right == None:
self.right = newnode
else:
newnode.right = self.right
self.right = newnode
defmaxHeight(root):if root isNone:
return0
q = []
q.append(root)
height = 0while(True):
nodeCount = len(q)
if nodeCount == 0 :
return height
height += 1while(nodeCount > 0):
node = q[0]
q.pop(0)
if node.left isnotNone:
q.append(node.left)
if node.right isnotNone:
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))
Comments