Prepared By : Uday Shah (HOD - IT)
E-Mail : rupareleducation@gmail.com
Contact No : 7600044051
Binary Tree
In a normal tree, every node can have any number of children. Binary tree is a special type of tree data structure in which every node can have a maximum of 2 children. One is known as left child and the other is known as right child.
A tree in which every node can have a
maximum of two children is called as Binary Tree.
In a binary tree, every node can have either 0 children or 1 child or 2
children but not more than 2 children.
Example
There are different types of binary trees and they are...
1. Strictly Binary Tree
In a binary tree, every node can have a maximum of two children. But in
strictly binary tree, every node should have exactly two children or none. That
means every internal node must have exactly two children. A strictly Binary
Tree can be defined as follows...
A binary tree in which every node has
either two or zero number of children is called Strictly Binary Tree
Strictly binary tree data structure is used to represent mathematical expressions.
2. Complete Binary Tree
In
a binary tree, every node can have a maximum of two children. But in strictly
binary tree, every node should have exactly two children or none and in
complete binary tree all the nodes must have exactly two children and at every
level of complete binary tree there must be 2level number of nodes. For example at level
2 there must be 22 = 4
nodes and at level 3 there must be 23 = 8 nodes.Binary Tree Traversals
When we wanted to display a binary tree, we need to follow some order
in which all the nodes of that binary tree must be displayed. In any binary
tree displaying order of nodes depends on the traversal method.
Displaying (or) visiting order of nodes in
a binary tree is called as Binary Tree Traversal.
There are three types of binary tree traversals.
1. In - Order Traversal
2. Pre - Order Traversal
3. Post - Order Traversal
Consider the following binary tree...
1. In - Order Traversal (
leftChild - root - rightChild )
In In-Order traversal, the root node is visited between left child and
right child. In this traversal, the left child node is visited first, then the
root node is visited and later we go for visiting right child node. This
in-order traversal is applicable for every root node of all subtrees in the
tree. This is performed recursively for all nodes in the tree.
That means here we have visited in the order of B - F - G - H - P - R - S - T - W - Y - Z using In-Order Traversal.
That means here we have visited in the order of B - F - G - H - P - R - S - T - W - Y - Z using In-Order Traversal.
2. Pre - Order Traversal ( root -
leftChild - rightChild )
In Pre-Order traversal, the root node is visited before left child and
right child nodes. In this traversal, the root node is visited first, then its
left child and later its right child. This pre-order traversal is applicable
for every root node of all subtrees in the tree.
That means here we have visited in the order of P - F - B - H - G - S - R - Y - T - W - Z using Pre-Order Traversal.
3. Post - Order Traversal (
leftChild - rightChild - root )
In
Post-Order traversal, the root node is visited after left child and right
child. In this traversal, left child node is visited first, then its right
child and then its root node. This is recursively performed until the right
most node is visited.
Here we have visited in the order of B - G - H - F - R - W - T - Z - Y - S - P using Post-Order Traversal.
Here we have visited in the order of B - G - H - F - R - W - T - Z - Y - S - P using Post-Order Traversal.
Best Of Luck
Pleaes share and give comment , Thank You
