In level order traversal of Binary Tree, we visit each node of the tree level by level. let’s say we have a tree as you see in the image given below.
here in the tree, there are 4 levels. So to find the level order of this tree we visit each level from top to bottom and left to right and traverse each node at that level.
First, we visit level 0 of the tree. so the level order of the tree is P
Now come to level 1. and in level 1 there are two node A and X so the level order of the tree become
P A X
then we visit level 2 so the new level order of the tree is
P A X T Z M G
then we visit level 3 so the new level order of the tree is
P A X T Z M G Y L F C
so this is the complete level order of the given tree.
Program to find the level order of the Binary tree using Python.
from collections import deque
class Node:
def __init__(self, value):
self.info = value
self.lchild = None
self.rchild = None
class BinaryTree:
def __init__(self):
self.root = None
def is_empty(self):
return self.root is None
def display(self):
self._display(self.root, 0)
print()
def _display(self,p,level):
if p is None:
return self._display(p.rchild, level+1)
print()
for i in range(level):
print(" ", end='')
print(p.info)
self._display(p.lchild, level+1)
def preorder(self):
self._preorder(self.root)
print()
def _preorder(self,p):
if p is None:
return print(p.info, " ", end='')
self._preorder(p.lchild)
self._preorder(p.rchild)
def inorder(self):
self._inorder(self.root)
print()
def _inorder(self,p):
if p is None:
return self._inorder(p.lchild)
print(p.info," ", end='')
self._inorder(p.rchild)
def postorder(self):
self._postorder(self.root)
print()
def _postorder(self,p):
if p is None:
return self._postorder(p.lchild)
self._postorder(p.rchild)
print(p.info," ",end='')
def level_order(self):
if self.root is None:
print("Tree is empty")
return
qu = deque()
qu.append(self.root)
while len(qu) != 0:
p = qu.popleft()
print(p.info + " ", end='')
if p.lchild is not None:
qu.append(p.lchild)
if p.rchild is not None:
qu.append(p.rchild)
def height(self):
return self._height(self.root)
def _height(self,p):
if p is None:
return 0
hL = self._height(p.lchild)
hR = self._height(p.rchild)
if hL > hR:
return 1 + hL
else:
return 1 + hR
def create_tree(self):
self.root = Node('p')
self.root.lchild = Node('Q')
self.root.rchild = Node('R')
self.root.lchild.lchild = Node('A')
self.root.lchild.rchild = Node('B')
self.root.rchild.lchild = Node('X')
##########################
bt = BinaryTree()
bt.create_tree()
bt.display()
print()
print("Preorder : ")
bt.preorder()
print("")
print("Inorder : ")
bt.inorder()
print()
print("Postorder : ")
bt.postorder()
print()
print("Level order : ")
bt.level_order()
print()
print("Height of tree is ", bt.height())
