What is a Binary tree? How to implement binary tree in C?

Binary Tree

Binary tree is one of widely used tree data structure in computer science. It is the simplest form of tree node where each node can have max of two children, known as left and right. Binary tree has numerous practical usages where one of the most widely used scenarios are items need to be arranged in sorted manner to optimize lookup efficiency. We will cover more topics in our next sections.

Binary Tree

Nodes in Binary Tree

This is the simplest form of tree structure with two pointers; one left and one right to point to the sub tree nodes. For a particular node, minimum child node can be zero and maximum children can be two.

Binary Tree Node

Binary Tree data structure

Designing a a data structure for a node is done by taking two pointer of type node. One to hold left child and another to point to right child. Node often contains a member variable to hold the value of its own. The data structure for a node of a binary tree looks like

struct node {
  struct node * left;
  struct node * right;
  int value;
};

Binary Tree node Allocation

When any node has no further child down the hierarchy, we put these pointers as NULL. Now if a node has no child then both node->left and node ->right is set to NULL. We generally create a new node setting both left and right to NULL. Later we asign left child pointer and then right child pointer once a new node comes for addition.

struct node * alloc_new_node (int value)
{
  struct node * new_node;
  /* Allocation with malloc */
  new_node  = (struct node *) malloc (sizeof(struct node));
  new_node ->value = <value>;
  new_node ->left = NULL;
  new_node ->right = NULL;
  return new_node;
}
struct node * alloc_new_node (int value)
{
  struct node * new_node;
  /* Allocation with calloc */
  new_node  = (struct node *) calloc (1, sizeof(struct node));
  new_node ->value = values 
}

Binary Tree node Addition

Now this new allocated node can be attached to an existing node in either in right side or left side. There will be a comparison between the value of this node to the parent node where it is getting added. If value is less than parent it can be added to left child else this should be added in right. This is the logic often used in binary search tree algorithm. We will discuss this more in our next topic.

The above logic is true when only root exists in the tree. But adding a node to populated binary tree is more complex. We should consider this logic right from root recursively till the condition matches.

struct node *node add_new_node (struct node *node, int value)
{
  if (node == NULL) { 
    node = add_new_node(value);
    return node;
  } else if (value = node -> value) {
    return NULL;
  } else if (value < node -> value) {
    if(node ->left == NULL) 
      node ->left  = add_new_node(value);
    else 
      add_new_node (node ->left, value);
  } else if (value > node -> value) {
    if(node ->right == NULL) 
      node ->right  = add_new_node(value);
    else 
      add_new_node (node ->right, value);
  }
}

Printing a Binary Tree

If we observe a binary tree we would find that lesser values are located at right side and greater values are at right side. This is the way we arranged it during the population time and thus tree elements are sorted in ascending order. Now printing entire binary tree would be in the same way as it has been arranged. We would consider printing left child first and then the right child. Printing is also recursive in nature and we should consider left child repeatedly till we reach most left node and print it one after another with this same logic.

void print_tree (struct node *node)
{
  if (node) {
    if(node ->left) {
      print_tree (node ->left);
    }
    printf("%d", node->value);
    if(node->right) {
      print_tree (node->right);
    }
  }
}

Total number of nodes

Computation starts from the root node and it goes recursively to the sub tree till it reaches the leaf node. In this way computation adds 1 for the node and further calls the same function for left and right sub trees. Leaf node does not have further sub child thus we return zero and last call returns. Finally top most parent call accumulates all the count and returns to the caller.

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

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions