# Construct Tree from given Postorder and Inorder traversals in C

## Construct Tree from given Postorder and Inorder Traversals

There are three types of traversals in a tree: Inorder, Preorder and Postorder traversal. A tree can be formed with any two tree traversals in which one of them being the in order traversal.

Postorder Traversal: We first  move to the left subtree and then to the right subtree and finally print the node.
Inorder Traversal: We move to the left subtree, then print the node and move to the right subtree. ## Algorithm For InOrder Traversal

• Traverse The Left subtree.
• Print the node.
• Traverse the right subtree.

## Algorithm For PostOrder Traversal

• Traverse the left subtree.
• Traverse the right subtree.
• Print the node.

## Algorithm for tree construction:

• Start with root node, which will be the last element in the postorder sequence
•  And find the boundary of its left and right subtree in the inorder sequence.
• To find the boundary, search for the index of the root node in the inorder sequence.
• All keys before the root node in the inorder sequence become part of the left subtree, and all the keys after the root node become part of the right subtree.
• Repeat the above step recursively for all the nodes in the tree and construct the tree. ## Code in C to Construct Tree from given Postorder and Inorder Traversals

`#include <stdio.h>#include <stdlib.h> struct Node{    int key;    struct Node *left, *right;}; struct Node* newNode(int key){    struct Node* node = (struct Node*)malloc(sizeof(struct Node));    node->key = key;    node->left = node->right = NULL;     return node;} void inorderTraversal(struct Node* root){    if (root == NULL) {        return;    }     inorderTraversal(root->left);    printf("%d ", root->key);    inorderTraversal(root->right);}struct Node* construct(int inorder[], int start, int end, int postorder[], int *pIndex){        if (start > end) {        return NULL;    }    struct Node* node = newNode(postorder[(*pIndex)--]);     for (int i = start; i <= end; i++)    {        if (inorder[i] == node->key) {            break;        }    }     node->right= construct(inorder, i + 1, end, postorder, pIndex);     node->left = construct(inorder, start, i - 1, postorder, pIndex);     return node;} struct Node* constructTree(int inorder[], int postorder[], int n){    int *pIndex = &n;    return construct(inorder, 0, n, postorder, pIndex);} int main(void){    int inorder[]    = { 40, 20, 10, 70, 50, 80, 30, 60 };    int postorder[] = { 40, 20, 70, 80, 50, 60, 30, 10 };    int n = sizeof(inorder)/sizeof(inorder);     struct Node* root = constructTree(inorder, postorder, n - 1);     printf("Inorder traversal is "); inorderTraversal(root);     return 0;}`
`Output :Inorder traversal is 40 20 10 70 50 80 30 60`