Tree

​Tree is a non linear and hierarchical Data Structure.

Trees are used to represent data containing a hierarchical relationship between elements e. g., records, family trees and table contents. A tree is the data structure that is based on hierarchical tree structure with set of nodes.

image001

  • Node: Each data item in a tree.
  • Root: First or top data item in hierarchical arrangement.
  • Degree of a Node: Number of subtrees of a given node.
    • Example: Degree of A = 3, Degree of E = 2
  • Degree of a Tree: Maximum degree of a node in a tree.
    • Example:  Degree of above tree = 3
  • Depth or Height: Maximum level number of a node + 1(i.e., level number of farthest leaf node of a tree + 1).
    • Example: Depth of above tree = 3 + 1= 4
  • Non-terminal Node: Any node except root node whose degree is not zero.
  • Forest: Set of disjoint trees.
  • Siblings: D and G are siblings of parent Node B.
  • Path: Sequence of consecutive edges from the source node to the destination node.
  • Internal nodes: All nodes those have children nodes are called as internal nodes.
  • Leaf nodes: Those nodes, which have no child, are called leaf nodes.
  • The depth of a node is the number of edges from the root to the node.
  • The height of a node is the number of edges from the node to the deepest leaf.
  • The height of a tree is the height of the root.

Trees can be used

  • for underlying structure in decision-making algorithms
  • to represent Heaps (Priority Queues)
  • to represent B-Trees (fast access to database)
  • for storing hierarchies in organizations
  • for file system

Binary Tree: A binary tree is a tree like structure that is rooted and in which each node has at most two children and each child of a node is designated as its left or right child. In this kind of tree, the maximum degree of any node is at most 2.

A binary tree T is defined as a finite set of elements such that

  • T is empty (called NULL tree or empty tree).
  • T contains a distinguished Node R called the root of T and the remaining nodes of T form an ordered pair of disjoint binary trees T1 and T2.

image002Any node N in a binary tree T has either 0, 1 or 2 successors. Level l of a binary tree T can have at most 2lnodes.

  • Number of nodes on each level i of binary tree is at most 2i
  • The number n of nodes in a binary tree of height h is atleast n = h + 1 and atmost n = 2h+1– 1, where h is the depth of the tree.
  • Depth d of a binary tree with n nodes >= floor(lg n)
    • d = floor(lg N) ; lower bound, when a tree is a full binary tree
    • d = n – 1  ; upper bound, when a tree is a degenerate tree

Creation of a binary tree

void insert(node ** tree, int val) {
 node *temp = NULL;
 if(!(*tree)) {
   temp = (node *)malloc(sizeof(node));
   temp->left = temp->right = NULL;
   temp->data = val;
   *tree = temp;
   return;
 }

 if(val < (*tree)->data) {
      insert(&(*tree)->left, val);
   } 
 else if(val > (*tree)->data) {
     insert(&(*tree)->right, val);
   }
 }

Search an element into binary tree

node* search(node ** tree, int val) {
 if(!(*tree)) {
   return NULL;
 }
 if(val == (*tree)->data) {
   return *tree;
  } 
 else if(val < (*tree)->data) {
    search(&((*tree)->left), val);
  } 
 else if(val > (*tree)->data){
    search(&((*tree)->right), val);
  }
 }

Delete an element from binary tree

void deltree(node * tree) {
 if (tree) {
   deltree(tree->left);
   deltree(tree->right);
   free(tree);
  }
}

Extended Binary Trees: 2.Trees or Strictly Binary Trees If every non-terminal node in a binary tree consist of non-empty left subtree and right subtree. In other words, if any node of a binary tree has either 0 or 2 child nodes, then such tree is known as strictly binary tree or extended binary tree or 2- tree. Complete Binary Tree: A complete binary tree is a tree in which every level, except possibly the last, is completely filled.

A Complete binary tree is one which have the following properties

  • Which can have 0, 1 or 2 children.
  • In which first, we need to fill left node, then right node in a level.
  • In which, we can start putting data item in next level only when the previous level is completely filled.
  • A complete binary tree of the height h has between 2h and 2(h+1)-1 nodes.

Tree Traversal: Three types of tree traversal are given below

  • Preorder
    • Process the root R.
    • Traverse the left subtree of R in preorder.
    • Traverse the right subtree of R in preorder.
/* Recursive function to print the elements of a binary tree with preorder traversal*/
void preorder(struct btreenode *node)
{
  if (node != NULL)
  {
    printf("%d", node->data);
    preorder(node->left);
    preorder(node->right);
  }
}
  • Inorder
    • Traverse the left subtree of R in inorder.
    • Process the root R.
    • Traverse the right subtree of R in inorder.
/* Recursive function to print the elements of a binary tree with inorder traversal*/
void inorder(struct btreenode *node)
{
  if (node != NULL)
  {
    inorder(node->left);   
    printf("%d", node->data);
    inorder(node->right);
  }
}
  • Postorder
    • Traverse the left subtree of R in postorder.
    • Traverse the right subtree of R in postorder.
    • Process the root R.
/* Recursive function to print the elements of a binary tree with postorder traversal*/
void postorder(struct btreenode *node)
{
  if (node != NULL)
  {
    postorder(node->left);   
    postorder(node->right);
    printf("%d", node->data);
  }
}

Breadth First Traversal (BFT): The breadth first traversal of a tree visits the nodes in the order of their depth in the tree. BFT first visits all the nodes at depth zero (i.e., root), then all the nodes at depth 1 and so on. At each depth, the nodes are visited from left to right. image003 Depth First Traversal (DFT): In DFT, one starts from root and explores as far as possible along each branch before backtracking. image004Perfect Binary Tree or Full Binary Tree: A binary tree in which all leaves are at the same level or at the same depth and in which every parent has 2 children. image005Here, all leaves (D, E, F, G) are at depth 3 or level 2 and every parent is having exactly 2 children.

  • Let a binary tree contain MAX, the maximum number of nodes possible for its height h. Then h= log(MAX + 1) –1.
  • The height of the Binary Search Tree equals the number of links of the path from the root node to the deepest node.
  • Number of internal/leaf nodes in a full binary tree of height h
    • 2h leaves
    • 2h -1 internal nodes

Expression Tree

An expression tree is a binary tree which represents a binary arithmetic expression. All internal nodes in the expression tree are operators, and leaf nodes are the operands. Expression tree will help in precedence relation of operators. (2+3)*4 and 2+(3*4) expressions will have different expression trees.

 

Example1: Recursive function for size (number of nodes) of a binary tree

int size(struct btreenode *node)
{
  if (node == NULL)
    return 0;
  else
    return (1 + size(node->left) + size(node->right));
}

Example2: Recursive function for Height of a tree

(Hieght is the length of path to the deepest node from the root node of tree)

int height(struct btreenode *node)
{ 
if (node == NULL) return 0; 
else return (1 + Max(height(node->left), height(node->right))); 
}

Example3: Print the elements of binary tree using level order traversal

void levelorder(struct node* root)
{
 int rear, front;
 struct node **queue = createqueue(&front, &rear);
 struct node *tempnode = root;
 while (temp_node)
 {
 printf("%d ", tempnode->data);
 if (tempnode->left)
 enqueue(queue, &rear, tempnode->left);
 if (tempnode->right)
 enqueue(queue, &rear, tempnode->right);
 tempnode = dequeue(queue, &front);
 }
}
struct node** createqueue(int *front, int *rear)
{
 struct node **queue = (struct node **) malloc(sizeof(struct node*)*n);
 *front = *rear = 0;
 return queue;
}