In this post we are going to write a short note on Tree Data Structure with all concept. As we know there are two type of Data structure Linear Data Structure and non-linear Data Structure. The Tree is a non-linear Data Structure means the element of the tree is does not follow any sequence. In tree data structure loop not allowed Means Tree must be Acyclic.

Tree Data Structure using C

A tree data structure is a collection of nodes (objects or entites) connected in a hierarchical manner. A tree is a set of non-empty finite elements. Tree consists a root node , internal node and leaf node. We can create a tree by using array as well as Linked list. Let's see basic terminology in Tree data structure.

Vertex of Tree : Each node of a tree is known as vertex of the tree. In vertex we represent an element.

Degree of Tree : In a tree, node having maximum number of degree is known as degree of tree.

Leaf Node : A node which have no any children known as Leaf Node.

Depth : The depth of binary tree is the maximum level of any leaf in the tree, means  the longest path from the Root Node to any leaf node is called depth of tree.

Construct a Tree using C Code

In C , we have two types of data type first one is built in data type (int,char,float etc.) and second one is user defined data type (struct, union).

So here we will use struct to create a blue print of a tree.

struct node{
  int data;
  struct node* leftNode;
  struct node* rightNode;
}

So, here we create two pointers variable which indicate the tree nodes. and the type of the pointer variable is node. and we also have an another variable called data, in which we store the data.

Function for creating a Node of tree in C

struct node* construtNode(int value){ 
     struct node *ref; 
     ref = (struct node*) malloc(sizeof(struct node*)); 
     ref->data = value; 
     ref->leftNode = NULL; 
     ref->rightNode = NULL; 
     return ref; 
}

Binary tree is the very important Data Structure. Let's see what is binary tree and it's types.

Binary tree in data structure

As the name suggest binary, means 2. In Binary tree every node have atmost 2 children or maximum two children. A node have zero children , one children and two children. But not more than two.

Types of Binary Tree

Full Binary Tree (Strict binary tree) : In FBT(Full binary tree) a node have either zero or atmost 2 Child but not one. In FBT Loop not allowed.

Almost Complete Binary Tree (ACBT) : In ACBT the element should be filled out from left side to right side. Means if a node have only right child then this tree is not a ACBT tree. It is a very most important topic , beacuse this will help us to create Heap like max heap, min heap etc.

Complete Binary Tree: in Complete Binary tree A node have atmost 2 children niether 0 or 1. And the level will be same. CBT(Complete binary tree) also known as Perfect Binary Tree.

Binary Search Tree (BST) : In binary Search tree, the Left Node must be less than from Root Node and Right Node must be Greater than from Root Node.

Predecessor and Successor in Binary Search Tree (BST)

Predecessor : The predecessor of a Binary Search tree is the greatest value of the left subtree.

Successor : The Successor of a binary tree is the smallest value present in right subtree.

Traversal in Tree data Structure

Traversal means visiting and exploring the each node for processing is called Traversal. There are three types of Tree traversal technique.

  • Preorder Traversal
  • Inorder Traversal
  • Postorder Traversal

Preorder Traversal : In Preorder Traversal first we visit Root Node and then , Left Node and after that Right Node.

N-> Root Node

L-> Left Node

R -> Right Node.

void preOrder(struct node* root){
  if(root !=NULL){
     printf('%d \n',root->data);
     preOrder(root->leftNode);
     preOrder(root->rightNode);
   }
}

Inorder Traversal : In inorder tree traversal, first we visit left node, then Root Node and after that Right Node.

void inOrder(struct node* root){
  if(root !=NULL){
     inOrder(root->leftNode);
     printf('%d \n',root->data);
     inOrder(root->rightNode);
   }
}

Postorder Traversal : In Postorder Traversal , first we visit Left Node, then Right Node after that Root Node. 

void postOrder(struct node* root){
  if(root !=NULL){
     postOrder(root->leftNode);
     postOrder(root->rightNode);
     printf('%d \n',root->data);
   }
}

Note * : If we traverse a Binary Search tree using Inorder Traversal, then we get a Sorted Array.

Application of Tree Data Structure

  • Build Complex XML parser Engine
  • Decision Making
  • Machine Learning
  • Represent Relationship
  • Files and Folder Organization.