An important category of general tree is Binary Tree. A binary tree can be defined as a finite collection of nodes where each node is having the property that it can have 0,1 or 2 children.
A binary tree may be empty known as Null tree or it contains a special node called the root of the tree and remaining nodes in the tree form the left and right binary sub-trees.
Here, the node A is the root of the binary tree which is the top of the tree.
B and C are the left and right sub-trees of the root A, respectively.
The left sub-tree namely B, having single node D.
The right sub-tree namely C having two nodes E and F.
Similar Binary tree
Two trees are called similar if both are having same structure but the elements in both the tree can be different as shown in fig. b
fig. b similar binary tree
Equivalent Binary tree
Two trees are called equivalent if both are having same structure and having the same content in their respective nodes.
Complete binary Tree
A binary tree is called complete if it contains the maximum number of nodes it can have as shown in fig. c
fig. c complete binary tree
On the other hand, a binary tree is said to be almost complete binary tree if all its levels are full except the last one as shown in fig. d
fig. d almost complete binary tree
In fig. c , at level k, there can be maximum 2^k nodes. therefore,
level 0 can have 2^0=1 node.
level 1 can have 2^1=2 nodes.
level 2 can have 2^2=4 nodes and so on.
Strictly Binary tree
A binary is called Strictly binary tree if all the non leaf nodes of the tree contains exactly two children.
It means , every non-leaf nodes contains left and right sub-tree.
It is also known as 2- tree or full Binary tree or extended binary tree.
It contains exactly 2n-1 nodes.