Binary Trees

A data structure is said to be linear if its elements form a sequence or linear lists.

Examples : ARRAYS , LINKED LISTS , STACKS , QUEUE

A data structure is said to be non-linear if its elements form a hierarchical order. Here the data items are appeared at various levels.

A tree is a hierarchical collection of nodes . The topmost node is known as the root of the tree. The tree has no parent node but may have child nodes . At the bottom of the tree are child nodes which have no children .Each node can have at most one link coming into it .  A tree can have any number of children .

TREE TERMINOLOGIES:

ROOT :  The top node in a tree is known as root or the node with no parent is known as a tree or the node whose indegree is 0 is known as a tree .  In the above picture A represents the root of the tree .

PARENT NODE : A node which has a child is known as a parent node or ancestor node .In the above tree A,B,E,G are parent nodes .

LEAF NODE : A node with no children is known as a leaf node .

                                                        Or

A node whose out degree is zero is known as a leaf node .

eg : Nodes N,O,P,Q are the leaf nodes in the above tree .

PATH : A sequence of nodes and edges connecting a node with the descendant is known as a path . Fr example , ABHN is a path connecting node A with node N .

SIBLNG : The children of the same node are known as siblings . In the above tree , nodes N,O are siblings since they are of the same parent node H .

INTERNAL NODE OR INNER NODE :

A node with atleast one child is known as internal node or inner node .eg : nodes B,E,G,H,K,L are the inner nodes in the above graph .

DEGREE : Degree of a node may be calculated as INDEGREE + OUT DEGREE .

INDEGREE : The number of edges arriving a node is known as indegree.

OUTDEGREE : Out degree is the number of edges leaving that node . 

                             The indegree of node A is 0 . The out degree of node A is 2 .

EDGE  : The connection  between one node to another node .

LEVEL : The level of a node refers to the distance from the root  , the root has level 0 and the level of any other node is more than the level of its parent .   

DEPTH : The depth of a node refers to the number of nodes in the path from root node to that node .

The depth of node B is 1 .

HEIGHT : The maximum level in the determines its height .

                              or

The height of the node is the length of the longest path to a leaf from that node

eg : The height of the above tree is 3 .

ANCESTORS AND DESCENDANTS :

If a path from node A to node B exists then A is called as ancestor of B and B is called the descendant of A .

Now let us know about the most important concept of trees . " BINARY TREES "

BINARY TREE :

In a binary tree , each node have at most two children . A binary tree is either empty or consist of a node called as a root together with two binary trees called left sub tree and right sub tree. A binary tree is easy to implement because they have fixed number of child links . Because of these characteristics binary trees are extensively used in various applications .

PROPERTIES OF A BINARY TREE :

• If h is the height of the binary tree then :
• Maximum number of leaf nodes are 2^h
• Maximum number of nodes are  2^h+1 - 1  

1.  If a binary tree contains m nodes at level i  it contains at most 2m nodes at level i+1 .
2. The total number of edges in a full binary tree with n nodes is n-1 .

Strictly Binary Tree :

If every non-leaf nodes has a non-empty left and right subtree then it is termed as a strictly binary tree .

A strictly binary tree with n leaves always has 2n-1 nodes .

Full Binary Tree :

A full binary tree of height h has all its leaves at  has all its leaves at level h or  all non-leaf nodes of a binary tree must have 2 children and leaf nodes should not have any children .

A full binary tree of height h has 2^h leaf nodes and 2^h - 1 non-leaf nodes .

COMPLETE BINARY TREE :

A complete binary tree of height h looks like a full binary tree down to level h-1 and the level h is filled  from left to right .

Representation of a binary tree :

A binary tree can be represented as both array and linked list .

Binary tree representation using array  :

Binary tree can also be stored by using array. If a node has an index i then the left child is found at node 2i+1 and the right child at node 2i+2 .

The parent index is found at index (i-1)/2

Array representation is good for a complete binary tree.

Representation using linked list :

In linked list representation , we use 3 fields :

• The left child 
• Data and 
• The right child .

If any subtree is empty, the corresponding  left and right child will store null values .

REPRESENTATION IN C:

typedef struct BinaryTree{

    int data;

 struct  BinaryTree *left_child;

 struct BinaryTree *right_child;

}

 C :

struct node

{

    int data;

    struct node *left;

    struct node *right;

};




/* newNode() allocates a new node with the given data and NULL left and

   right pointers. */




struct node* newNode(int data)

{




  // Allocate memory for new node




  struct node* node = (struct node*)malloc(sizeof(struct node));

  // Assign data to this node




  node->data = data;

  // Initialize left and right children as NULL




  node->left = NULL;

  node->right = NULL;

  return(node);

}

int main()

{

  /*create root*/

  struct node *root = newNode(1); 

  /* following is the tree after above statement

        1

      /   \

     NULL  NULL 

  */

   

  root->left   = newNode(2);

  root->right  = newNode(3);

  /* 2 and 3 become left and right children of 1

           1

         /   \

        2      3

     /    \    /  \

    NULL NULL NULL NULL

  */

  root->left->left  = newNode(4);

  /* 4 becomes left child of 2

           1

       /       \

      2          3

    /   \       /  \

   4    NULL  NULL  NULL

  /  \

NULL NULL

*/

getchar();




 return 0;

Advantages of using linked list :

• Insertion and deletion requires no data movement and no movement of nodes except rearrangement of pointers .

Disadvantage of using linked list :

• For  a given node structure , it is difficult to find its parent.
• Memory spaces are wasted for storing NULL pointers - for the nodes which have no subtree .

TREE TRAVERSAL METHODS :

A tree traversal is a method of visiting every node in a tree. There are common ways to traverse a binary tree .

1. INORDER TRAVERSAL
2. PREOREDER TRAVERSAL
3. POST ORDER TRAVERSAL 
4. LEVEL OREDER TRAVERSAL

Recursive traversal algorithm :

1.  Inorder traversal :

In the case of inorder traversal , the root oeach subtree is visited after its left subtree has been visited but before the right subtree has been visited .

STEPS :

• Visit the left subtree using inorder
• Visit the root
• Visit the right subtree using inorder

algorithm :

void inorder(node *root){

if(root!=NULL){

 inorder(root->lchild);

printf("%d",data);

inorder(root->rchild);

}

}

2. Preorder traversal :

In this traversal , each root node is visited before the left and right child ahas been visited .

STEPS:

• Visit the root .
• Visit the left subtree
• Visit the right subtree

code :

void preorder(node *root){

if(root!=NULL){

  preorder(root->data);

 preorder(root->lchild);

 preorder(root->rchild);

}

}

3. Postorder traversal :

In this traversal , the root is visted only after the left and right child has been visited .

STEPS: 

• Visit the left child.
• Visit the right child
• Visit the root.

Algorithm :

void postorder(node *root){

 if(root!=null){

   

     postorder(root->lchild);

  postorder(root->rchild);

  postorder(root->data);

}

}

4. Level order traversal :

In level order traversal , the nodes are visited level by level starting from root going from left to right .

Building a binary tree from traversal pair :

Sometimes it isrequired to contruct a binary tree if its traversal is known . From a single traversal it might not be possible to construct a binary tree . However any two of the traversals given a binary tree can be constructed easily .

• Inorder - preorder
• Inorder-postorder
• Inorder-levelorder