A

##

It is a finite set of nodes that is either empty or either consists of a distinguished node known as root and 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.

###

####

In a binary tree, the maximum number of nodes on any level I is 2

where I >= 0

####

In a binary tree of height H, the maximum number of nodes possible is 2

####

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.

####

For any binary tree with n nodes, the maximum height possible is n and 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.

####

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.

####

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

###

####

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 2n - 1 node.

####

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 original nodes are called internal nodes.

####

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

####

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)]

####

**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 either consists of a distinguished node known as root and 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 2^{i}####
__Property second__

In a binary tree of height H, the maximum number of nodes possible is 2^{H}- 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 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 ifn = 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, ifn0 = 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 2n - 1 node.####
__What is 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 original nodes are called internal nodes.**The number of edges traversed from that node to the root node is called the path length of a node.**__Path length:__**it's is a sum of path lengths of all internal nodes.**__Internal path length:__**it's a sum of path lengths of all external nodes.**__External path length:__**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.**__Property:__####
__What is 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 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 programming language.__

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())

## 0 Comments