Binary Tree | Implementation

In this blog, we will discuss the implementation of Binary Tree using C.

Now as we have discussed earlier Binary Tree and its types.

A binary tree is a rooted tree where the maximum degree of any node is 2.

---

Before moving forward we need to know about Tree traversals because unlike linear Data Structures that have only one logical way to traverse them, trees can be traversed in many ways.

Example:

                1
               / \
              2   3
             / \
            4   5

Depth First Traversals:

1. Inorder (Left, Root, Right): 4 2 5 1 3

2. Preorder (Root, Left, Right): 1 2 4 5 3

3. Postorder (Left, Right, Root): 4 5 2 3 1

---

Implementation:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
  int data;
  struct node *left;
  struct node *right;
} node;

node *create()
{
    node *p;
    int x;
    printf("Enter data( -1 for no node):");
    scanf("%d",&x);

    if(x==-1)
	return NULL;

    p=(node*)malloc(sizeof(node));
    p->data=x;
    printf("Enter left child of %d:\n",x);
    p->left=create();
    printf("Enter right child of %d:\n",x);
    p->right=create();
    return p;
}

void preorder(node *t)
{
  if(t!=NULL)
  {
    printf("  %d",t->data);
    preorder(t->left);
    preorder(t->right);
  }
}
void inorder(node *t)
{
  if(t!=NULL)
  {
    inorder(t->left);
    printf("  %d",t->data);
    inorder(t->right);
  }
}
void postorder(node *t)
{
  if(t!=NULL)
  {
    postorder(t->left);
    postorder(t->right);
    printf("  %d",t->data);
  }
}
void main()
{
  node *root;
 
  root=create();
  printf("\nThe preorder traversal of tree is: ");
  preorder(root);
  printf("\nThe inorder traversal of tree is: ");
  inorder(root);
  printf("\nThe postorder traversal of tree is: ");
  postorder(root);
  getch();
}

Output:
Enter data( -1 for no node):90
Enter left child of 90:
Enter data( -1 for no node):12
Enter left child of 12:
Enter data( -1 for no node):34
Enter left child of 34:
Enter data( -1 for no node):-1
Enter right child of 34:
Enter data( -1 for no node):-1
Enter right child of 12:
Enter data( -1 for no node):-1
Enter right child of 90:
Enter data( -1 for no node):-1

The preorder traversal of tree is:   90  12  34
The inorder traversal of tree is:   34  12  90
The postorder traversal of tree is:   34  12  90

---

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science