C Program to Construct Binary Tree from Postorder and Inorder

This C Program Build Binary Tree if Inorder or Postorder Traversal as Input.

Here is source code of the C Program to Build Binary Tree if Inorder or Postorder Traversal as Input. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C  Program to Build Binary Tree if Inorder or Postorder Traversal as Input

```
 *
```
```
 *                     40
```
```
 *                    /  \
```
```
 *                   20   60
```
```
 *                  /  \   \
```
```
 *                 10  30   80
```
```
 *                           \
```
```
 *                           90    
```

 *             (Given Binary Search Tree)

```
 */
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct btnode
```
```
{
```
```
    int value;
```
```
    struct btnode *l;
```
```
    struct btnode *r;
```
```
}*root = NULL, *temp = NULL;
```
```
 
```
```
typedef struct btnode N;
```
```
void insert();
```
```
N* bt(int arr[],int,int);
```
```
N* new(int);
```
```
void inorder(N *t);
```
```
void create();
```
```
void search(N *t);
```
```
void preorder(N *t);
```
```
void postorder(N *t);
```
```
 
```
```
void main()
```
```
{
```
```
    int ch, i, n;
```

    int arr[] = {10, 20, 30, 40, 60, 80, 90};

```
    n = sizeof(arr) / sizeof(arr[0]);
```
```
 
```
```
    printf("\n1- Inorder\n");
```
```
    printf("2 - postorder\n");
```
```
    printf("\nEnter choice : ");
```
```
    scanf("%d", &ch);
```
```
    switch (ch)
```
```
    {
```
```
    case 1:
```
```
        root = bt(arr, 0, n-1); 
```

        printf("Given inorder traversal as input\n");

```
        for (i = 0;i< = 6;i++)
```
```
            printf("%d->", arr[i]);
```

        printf("\npreorder traversal of tree\n");

```
        preorder(root);
```

        printf("\ninorder traversal of tree\n");

```
        inorder(root);
```

        printf("\npostorder traversal of tree\n");

```
        postorder(root);
```
```
        break;
```
```
    case 2:
```
```
        insert();
```

        printf("\npreorder traversal of tree\n");

```
        preorder(root);
```

        printf("\nInorder traversal of tree\n");

```
        inorder(root);
```

        printf("\npostorder traversal of tree\n");

```
        postorder(root);
```
```
        break;
```

        default:printf("enter correct choice");

```
    }
```
```
}
```
```
 
```
```
/* To create a new node */
```
```
N* new(int val)
```
```
{
```
```
    N* node = (N*)malloc(sizeof(N));
```
```
 
```
```
    node->value = val;
```
```
    node->l = NULL;
```
```
    node->r  =  NULL;
```
```
    return node;
```
```
}
```
```
 
```

/* To create a balanced binary search tree */

```
N* bt(int arr[], int first, int last)
```
```
{
```
```
    int mid;
```
```
 
```
```
    N* root = (N*)malloc(sizeof(N));
```
```
    if (first > last)
```
```
        return NULL;
```
```
    mid = (first + last) / 2;
```
```
    root = new(arr[mid]);
```
```
    root->l = bt(arr, first, mid - 1);
```
```
    root->r = bt(arr, mid + 1, last);
```
```
    return root;
```
```
}
```
```
 
```
```
/* Insert a node in the tree */
```
```
void insert()
```
```
{
```

    int arr1[] = {10, 30, 20, 90, 80, 60, 40}, i;

```
 
```

    printf("Given post order traversal array\n");

```
    for (i = 0;i <= 6;i++)
```
```
    {
```
```
        printf("%d->", arr1[i]);
```
```
     }
```
```
    for (i = 6;i >= 0;i--) 
```
```
    {
```
```
        create(arr1[i]);
```
```
        if (root =  = NULL)
```
```
            root = temp;
```
```
        else
```
```
            search(root);
```
```
    }
```
```
}
```
```
 
```
```
/*Create a node */
```
```
void create(int data)
```
```
{
```
```
    temp = (N *)malloc(1*sizeof(N));
```
```
 
```
```
    temp->value = data;
```
```
    temp->l = temp->r = NULL;
```
```
}
```
```
 
```

/* Search for the appropriate position to insert the new node */

```
void search(N *t)
```
```
{
```

    if ((temp->value>t->value)&&(t->r != NULL))

```
        search(t->r);
```

    else if ((temp->value>t->value)&&(t->r  == NULL))

```
        t->r = temp;
```

    else if ((temp->value<t->value)&&(t->l != NULL))

```
        search(t->l);
```

    else if ((temp->value<t->value)&&(t->l == NULL))

```
        t->l = temp;
```
```
}
```
```
 
```
```
/* to display inorder of tree */
```
```
void inorder(N *t)
```
```
{
```
```
    if (t->l != NULL)
```
```
        inorder(t->l);
```
```
    printf("%d->", t->value);
```
```
    if (t->r != NULL)
```
```
        inorder(t->r);
```
```
}
```
```
 
```

/* to display preorder traversal of tree */

```
void preorder(N *t) 
```
```
{
```
```
    printf("%d->", t->value);
```
```
    if (t->l != NULL)
```
```
        inorder(t->l);
```
```
    if (t->r != NULL)
```
```
        inorder(t->r);
```
```
}
```
```
 
```

/* to display postorder traversal of tree */

```
void postorder(N *t) 
```
```
{
```
```
    if (t->l != NULL)
```
```
        inorder(t->l);
```
```
    if (t->r != NULL)
```
```
        inorder(t->r);
```
```
    printf("%d->", t->value);
```
```
}
```

$ cc trees.c
$ a.out
 
1- Inorder
2 - postorder
Enter choice : 1
Given inorder traversal as input
10->20->30->40->60->80->90
preorder traversal of tree
40->10->20->30->60->80->90
inorder traversal of tree
10->20->30->40->60->80->90
postorder traversal of tree
10->20->30->60->80->90->40
 
$ a.out
1 - Inorder
2 - postorder
Enter choice : 2
Given post order traversal array
10->30->20->90->80->60->40
preorder traversal of tree
40->10->20->30->60->80->90
Inorder traversal of tree
10->20->30->40->60->80->90
postorder traversal of tree
10->20->30->60->80->90->40

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Check String is Palindrome using Stack

» Next - C Program to Find Minimum and Maximum Element in Binary Search Tree

Related Posts:

Practice Computer Science MCQs
Practice Design & Analysis of Algorithms MCQ
Check Data Structure Books
Apply for Computer Science Internship
Check Computer Science Books

Recommended Articles: