A binary tree is a nonlinear data structure in which a node cannot have more than two child nodes. it means if in a tree each node is either a leaf node or has one or two child nodes then this tree is called a binary tree.
What is a binary tree in Data structures?
It is a finite set of nodes that is either empty or consists of a distinguished node known as root and the remaining nodes are partitioned into two disjoint sets T1 and T2 and both of them are binary trees.
The T1 is called the left subtree and T2 is called the right subtree.
Properties of Binary Tree in Data Structure
Property first
In a binary tree, the maximum number of nodes on any level I is 2i
where I >= 0
Property second
In a binary tree of height H, the maximum number of nodes possible is 2H – 1
Property third
In a binary tree of height H, the minimum number of nodes possible is H. because the minimum number of nodes possible at any level is 1 in a tree of height H and there are H levels.
and the tree which has nodes equal to their height are called skew trees.
Property fourth
For any binary tree with n nodes, the maximum height possible is n and the minimum height possible is [ log2(n+1)]
because the height can’t be more than n so there should be at least one node at every level and if the height is H then the maximum number of nodes possible is 2H – 1.
Property fifth
In a non-empty binary tree if
n = number of nodes
e = number of edges
then e = n -1
Because every node has exactly one parent except the root node and n-1 nodes have exactly one parent so there is only one edge between a parent and child.
if the n = 1 and e = 0 then n = 1 so the property is true.
Property sixth
In a non-empty binary tree, if
n0 = number of nodes with no child
n2 = number of nodes with 2 children then n0 = n2 + 1
Types of Binary Trees
- Strictly binary tree
- Extended binary tree
- Full binary tree
- Complete binary tree
What is a Strictly binary tree
A binary tree in which each node is either a left node or has two children is called a strictly binary tree and a strictly binary tree with n-leaf nodes has n-1 non-leaf nodes and a total of 2n – 1 nodes.
What is an Extended Binary Tree?
In a binary tree if each empty subtree is replaced by a special node then the resulting tree is called an extended binary tree or 2-tree. and the special nodes are called external nodes and the original nodes are called internal nodes.
Path length: The number of edges traversed from that node to the root node is called the path length of a node.
Internal path length: it is a sum of the path lengths of all internal nodes.
External path length: it’s a sum of the path lengths of all external nodes.
Property: In an extended binary tree, if E is the external path length, I is the internal path length and n is the number of internal nodes, then E = I + 2n.
What is a Full binary tree?
A binary tree in which each level has the maximum number of nodes is called a full binary tree. and if H is the height of a tree then the binary tree will have 2H – 1 node. then the height of a full binary tree is log2(n+1).
What is a Complete binary tree?
In a complete binary tree, all levels have a maximum number of nodes except possibly the last level, and in the last level, the number of nodes ranges from 1 to 2H – 1 and all these nodes are towards the left.
the height of a complete binary tree = [ log2(n+1)]
Program to implement a 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())
