Types of Tree Data Structure
General tree: The general tree is one of the types of tree data structure. In the general tree, a
node can have either 0 or maximum n number of nodes. There is no restriction imposed on
the degree of the node
BINARY TREE:
A 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 a 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 Binary Tree.
Strictly Binary Tree:
In strictly binary tree, every node should have exactly two children or none. That means
every internal node must have exactly two children.
A binary tree in which every node has either two or zero number of children is called Strictly
Binary Tree
Strictly binary tree is also called as Full Binary Tree or Proper Binary Tree or 2-Tree.
Complete Binary Tree:
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.
A binary tree in which every internal node has exactly two children and all leaf nodes are at
same level is called Complete Binary Tree.
Extended Binary Tree:
A binary tree can be converted into Full Binary tree by adding dummy nodes to existing
nodes wherever required.
The full binary tree obtained by adding dummy nodes to a binary tree is called as Extended
Binary Tree.
Skewed Binary Tree:
If a tree which is dominated by left child node or right child node, is said to be a Skewed
Binary Tree.
In a skewed binary tree, all nodes except one have only one child node. The remaining node
has no child.
Perfect Binary Tree
A perfect binary tree is a type of binary tree in which every internal node has exactly two
child nodes and all the leaf nodes are at the same level.
Binary Search Tree
A Binary Search Tree is a Binary Tree where every node's left child has a lower value, and
every node's right child has a higher value.
Heap
A heap is a tree-like data structure in which the tree is a complete binary tree that satisfies the
heap property. According to the heap property, all the children of a given node must be
greater than the parent node, or all the children must be smaller than the parent node.
BINARY TREE TRAVERSALS:
Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.
binary trees can be traversed in different ways.
1. In - Order Traversal
2. Pre - Order Traversal
3. Post - Order Traversal
In - Order Traversal (left -Visit- right ):
In this traversal, the left child node is visited first, then the root node is visited and later we
go forvisiting the right child node. This in-order traversal is applicable for every root node of
allsub trees in the tree. This is performed recursively for all nodes in the tree.
Algorithm for inorder Traversal
inorder(root)
inorder(root->left);
visit(root);
inorder(root->right);
Algorithm for preorder Traversal
preorder(root)
visit(root);
preorder(root->left);
preorder(root->right);
Algorithm for postorder Traversal
postorder(root)
postorder(root->left);
postorder(root->right);
visit(root);
Insertion in to Binary search Tree
To insert an element in a BST, we need to maintain the rule that the left subtree is lesser than
the root, and the right subtree is larger than the root. We keep going to either the right subtree
or the left subtree depending on the value and when we reach a point left or right subtree is
null, we put the new node there.
Check the value to be inserted (say X) with the value of the current node (say val) we
are in:
If X is less than val move to the left subtree.
Otherwise, move to the right subtree.
Once the leaf node is reached, insert X to its right or left based on the relation
between X and the leaf node’s value .
Algorithm
insertBST(root,value)
{
create_ newnode();// create memory for new node
if(root= =NULL) // check the tree is empty ,if so set the newnode as root
{
root=new node;
}
else if(value < root) //if the new node is less than root ,recursively call the insert function
with left subtree
{
insert(root->left,value);
}
else
{
insert(root->right,value);// // if the new node is greater than root ,recursively call the insert
function with right subtree
}}
Deletion from Binary Search Tree
Deleting a value from a BST involves first searching for the value in the tree. If the value is
found, there are three cases to consider:
a. If the node has no children, it is simply removed from the tree.
b. If the node has one child, the child takes the place of the deleted node.
c. If the node has two children, then, find the inorder successor of the node to be deleted. then
replace the deleted node with the inorder successor node and rebalance the tree.
Algorithm
delete(root, int x)
//searching for the item to be deleted
if (root == NULL)
return NULL;
if (x > root -> data)
delete(root -> right, x);
else if (x < root -> data)
delete(root -> left, x);
else
//No Child node
if (root -> left== NULL && root -> right == NULL)
free(root);
return NULL;
//One Child node
else if (root -> left== NULL || root -> right == NULL) {
if (root -> left== NULL)
temp = root -> right;
else
temp = root -> left;
free(root);
return temp;
//Two Children
else {
find_minimum(root -> right);
root -> data = temp -> data;
root -> right= delete(root -> right, temp -> data);
Search for a key in a given Binary Search Tree:
Searching for some specific node in binary search tree is easy due to the fact that, element in
BST are stored in a particular order.
1. Compare the element with the root of the tree.
2. If the item is matched then return the location of the node.
3. Otherwise check if item is less than the element present on root, if so then move to the
left sub-tree.
4. If not, then move to the right sub-tree.
5. Repeat this procedure recursively until match found.
6. If element is not found then return NULL.
algorithm
search(struct node* root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
return root;
// Key is greater than root's key
if (root->key < key)
return search(root->right, key);
// Key is smaller than root's key
return search(root->left, key);
}
Expression tree
The expression tree is a tree used to represent the various expressions. The tree
data structure is used to represent the expressional statements. In this tree, the
internal node always denotes the operators.
