Technical Point.

Tree in Data Structure

In linear data structure data is organized in sequential order and in non-linear data structure data is organized in random order. A tree is a very popular non-linear data structure used in a wide range of applications.

Tree is a non-linear data structure which organizes data in hierarchical structure and this is a recursive definition.

A tree data structure can also be defined as follows...

Tree data structure is a collection of data (Node) which is organized in hierarchical structure recursively

In tree data structure, every individual element is called as Node. Node in a tree data structure stores the actual data of that particular element and link to next element in hierarchical structure.

In linear data structure, data is organized in sequential order and in non-linear data structure, data is organized in random order. Tree is a very popular data structure used in wide range of applications. A tree data structure can be defined as follows.

Tree is a non-linear data structure which organizes data in hierarchical structure and this is a recursive definition.

A tree is a collection of elements called nodes. Each node contains some value or element. In a tree data structure, if we have N number of nodes then we can have a maximum of N-1 number of links. We will use the term node, rather than vertex with binary tree. Node is the main component of any tree structure. It stores the actual data along with links to other nodes.

In a tree data structure, if we have N number of nodes then we can have a maximum of N-1 number of links.

Example

Terminology

In a tree data structure, we use the following terminology...

1. Root

In a tree data structure, the first node is called as Root Node. Every tree must have a root node. We can say that the root node is the origin of the tree data structure. In any tree, there must be only one root node. We never have multiple root nodes in a tree.

2. Edge

In a tree data structure, the connecting link between any two nodes is called as EDGE.
In a tree with 'N' number of nodes there will be a maximum of 'N-1' number of edges.

3. Parent

In a tree data structure, the node which is a predecessor of any node is called as PARENT NODE.
In simple words, the node which has a branch from it to any other node is called a parent node.
 Parent node can also be defined as "The node which has child / children".

4. Child

In a tree data structure, the node which is descendant of any node is called as CHILD Node.
 In simple words, the node which has a link from its parent node is called as child node.
In a tree, any parent node can have any number of child nodes. In a tree,
 all the nodes except root are child nodes.

5. Siblings

In a tree data structure, nodes which belong to same Parent are called as SIBLINGS.
 In simple words, the nodes with the same parent are called Sibling nodes.

6. Leaf

In a tree data structure, the node which does not have a child is called as LEAF Node.
 In simple words, a leaf is a node with no child.

In a tree data structure, the leaf nodes are also called as External Nodes.
External node is also a node with no child. In a tree, leaf node is also called as 'Terminal' node.

7. Internal Nodes

In a tree data structure, the node which has atleast one child is called as INTERNAL Node.
 In simple words, an internal node is a node with atleast one child.

In a tree data structure, nodes other than leaf nodes are called as Internal Nodes. 
The root node is also said to be Internal Node if the tree has more than one node.
 Internal nodes are also called as 'Non-Terminal' nodes.

8. Degree

In a tree data structure, the total number of children of a node is called as DEGREE of that Node.
In simple words, the Degree of a node is total number of children it has.
The highest degree of a node among all the nodes in a tree is called as 'Degree of Tree'

9. Level

In a tree data structure, the root node is said to be at Level 0 and the children of root
node are at Level 1 and the children of the nodes which are at Level 1 will be at
Level 2 and so on... In simple words, in a tree each step from top to bottom is called
 as a Level and the Level count starts with '0' and incremented by one at each level (Step).

10. Height

In a tree data structure, the total number of edges from leaf node to a particular node in the longest path is called as HEIGHT of that Node. In a tree, height of the root node is said to be height of the tree. In a tree, height of all leaf nodes is '0'.

11. Depth

In a tree data structure, the total number of egdes from root node to a particular
node is called as DEPTH of that Node.
In a tree, the total number of edges from root node to a leaf node in the longest 
path is said to be Depth of the tree.
In simple words, the highest depth of any leaf node in a tree is said to be
depth of that tree. In a tree, depth of the root node is '0'.

12. Path

In a tree data structure, the sequence of Nodes and Edges from one node to another
node is called as PATH between that two Nodes. Length of a Path is total number
 of nodes in that path. In below example the path A - B - E - J has length 4.

13. Sub Tree

In a tree data structure, each child from a node forms a subtree recursively.
Every child node will form a subtree on its parent node.

Binary Tree 

In a normal tree, every node can have any number of children. 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.

In a binary tree, every node can have either 0 children or 1 child or 2 children but not more than 2 children.

A binary tree is a tree which can be empty or can have a root R with at most 2 children. 

Each of these children then can be an empty tree or can again contain at most 2 children 

to form a binary tree. Following is an example of binary tree

A binary tree is a tree in which the
       number of nodes can have at most
       two children.

  In other words,a binary tree is a tree
       in which every node has either 0 or 2
       children (i.e., 0,1,2).

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

 Strict binary tree is a tree with whome
        every node have either zero (0) or two
        (2) children.

  In strict binary tree if number of leaf
       node will be n then the total number of
       nodes present in this tree will be (2n-1)
       nodes.

---

Strictly binary tree is also called as Full Binary Tree or Proper Binary Tree or 2-Tree

---

Strictly binary tree data structure is used to represent mathematical expressions.

Example

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.

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.

 A binary tree is said to be complete  binary tree if all the leaf nodes of the
         tree are at same level.

    Complete binary tree are mainly used
         in heap based data Structure.

   The node in the complete binary tree
         are inserted from left to right in one
         level at a time.

---

Complete binary tree is also called as Perfect Binary Tree

---

3. Extended Binary Tree

A binary tree can be converted into Full Binary tree by adding dummy nodes to existing nodes wherever required

A binary tree can be converted into an extended binary tree by adding new nodes to its

 leaf nodes and to the nodes that have only one child. These new nodes are added in such

 a way that all the nodes in the resultant tree have either zero or two children. It is also called 2 - tree.

The full binary tree obtained by adding dummy nodes to a binary tree is called as Extended Binary Tree.

In above figure, a normal binary tree is converted into full binary tree by adding dummy nodes (In pink colour).

Binary Tree Traversals

Tree traversal is the process of visiting each node in the tree exactly once. 

Visiting each node in a graph should be done in a systematic manner. 

If search result in a visit to all the vertices, it is called a traversal. 

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 the 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 the 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.
In the above example of a binary tree, first we try to visit left child of root node 'A',
 but A's left child 'B' is a root node for left subtree. so we try to visit its (B's) left child 'D' and
again D is a root for subtree with nodes D, I and J. So we try to visit its left child 'I' and
it is the leftmost child. So first we visit 'I' then go for its root node 'D' and later we visit D's
right child 'J'. With this we have completed the left part of node B. Then visit 'B' and next
 B's right child 'F' is visited. With this we have completed left part of node A.
Then visit root node 'A'. With this we have completed left and root parts of node A.
 Then we go for the right part of the node A. In right of A again there is a subtree
with root C. So go for left child of C and again it is a subtree with root G. But G does
 not have left part so we visit 'G' and then visit G's right child K. With this we have
completed the left part of node C. Then visit root node 'C' and next visit C's right
child 'H' which is the rightmost child in the tree. So we stop the process.

That means here we have visited in the order of I - D - J - B - F - A - G - K - C - H using In-Order Traversal.

In-Order Traversal for above example of binary tree is

I - D - J - B - F - A - G - K - C - H

2. Pre - Order Traversal ( root - leftChild - rightChild )

In Pre-Order traversal, the root node is visited before the 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.
In the above example of binary tree, first we visit root node 'A' then visit its left child 'B'
which is a root for D and F. So we visit B's left child 'D' and again D is a root for I and J.
 So we visit D's left child 'I' which is the leftmost child. So next we go for visiting D's
 right child 'J'. With this we have completed root, left and right parts of node D and root,
 left parts of node B. Next visit B's right child 'F'. With this we have completed root and
left parts of node A. So we go for A's right child 'C' which is a root node for G and H.
 After visiting C, we go for its left child 'G' which is a root for node K. So next we visit
left of G, but it does not have left child so we go for G's right child 'K'. With this,
we have completed node C's root and left parts. Next visit C's right child 'H' which is
 the rightmost child in the tree. So we stop the process.

That means here we have visited in the order of A-B-D-I-J-F-C-G-K-H using Pre-Order Traversal.

Pre-Order Traversal for above example binary tree is

A - B - D - I - J - F - C - G - K - H

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 I - J - D - F - B - K - G - H - C - A using Post-Order Traversal.

Post-Order Traversal for above example binary tree is

I - J - D - F - B - K - G - H - C - A

Program to Create Binary Tree and display using In-Order Traversal - C Programming

#include
#include

struct Node{
   int data;
   struct Node *left;
   struct Node *right;
};

struct Node *root = NULL;
int count = 0;

struct Node* insert(struct Node*, int);
void display(struct Node*);

void main(){
   int choice, value;
   clrscr();
   printf("\n----- Binary Tree -----\n");
   while(1){
      printf("\n***** MENU *****\n");
      printf("1. Insert\n2. Display\n3. Exit");
      printf("\nEnter your choice: ");
      scanf("%d",&choice);
      switch(choice){
	 case 1: printf("\nEnter the value to be insert: ");
		 scanf("%d", &value);
		 root = insert(root,value);
		 break;
	 case 2: display(root); break;
	 case 3: exit(0);
	 default: printf("\nPlease select correct operations!!!\n");
      }
   }
}

struct Node* insert(struct Node *root,int value){
   struct Node *newNode;
   newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode->data = value;
   if(root == NULL){
      newNode->left = newNode->right = NULL;
      root = newNode;
      count++;
   }
   else{
      if(count%2 != 0)
	 root->left = insert(root->left,value);
      else
	 root->right = insert(root->right,value);
   }
   return root;
}
// display is performed by using Inorder Traversal
void display(struct Node *root)
{
   if(root != NULL){
      display(root->left);
      printf("%d\t",root->data);
      display(root->right);
   }
}

Output