Construct Tree from given Postorder and Inorder traversals in C

March 19, 2025

Construct Tree from given Postorder and Inorder Traversals

On this page we wiil discuss about how to construct tree from given postorder and inorder traversals in C .

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.

postorder inorder traversal

Tree From Given Postorder and Inorder Traversal

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.
Construct Tree from given Postorder and Inorder Traversals in C++

Tree Traversals: Inorder Postorder Preorder

BST: Binary Search Tree Program

BST: Search a node in Binary Search Tree

Construct Tree from given Inorder and Preorder traversals

Construct Tree from given Postorder and Preorder traversal

Code in C to Construct Tree from given Postorder and Inorder Traversals

Run 
#include <stdio.h>
#include <stdlib.h>
 
// Data structure to store a binary tree node
struct Node
{
    int key;
    struct Node *left, *right;
};
 
// Function to create a new binary tree node having a given key
struct Node* newNode(int key)
{
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = node->right = NULL;
 
    return node;
}
 
// Recursive function to perform inorder traversal on a given binary tree
void inorderTraversal(struct Node* root)
{
    if (root == NULL) {
        return;
    }
 
    inorderTraversal(root->left);
    printf("%d ", root->key);
    inorderTraversal(root->right);
}
 
// Recursive function to perform postorder traversal on a given binary tree
void postorderTraversal(struct Node* root)
{
    if (root == NULL) {
        return;
    }
 
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->key);
}
 
// Recursive function to construct a binary tree from a given
// inorder and postorder traversals
struct Node* construct(int inorder[], int start, int end,
                    int postorder[], int *pIndex)
{
    // base case
    if (start > end) {
        return NULL;
    }
 
    // Consider the next item from the end of a given postorder sequence.
    // This value would be the root node of the subtree formed by the sequence
    // inorder[start, end].
    struct Node* node = newNode(postorder[(*pIndex)--]);
 
    // search the current node index in inorder sequence to determine
    // the boundary of the left and right subtree of the current node
    int i;
    for (i = start; i <= end; i++)
    {
        if (inorder[i] == node->key) {
            break;
        }
    }
 
    // recursively construct the right subtree
    node->right= construct(inorder, i + 1, end, postorder, pIndex);
 
    // recursively construct the left subtree
    node->left = construct(inorder, start, i - 1, postorder, pIndex);
 
    // return the current node
    return node;
}
 
// Construct a binary tree from inorder and postorder traversals.
// This function assumes that the input is valid, i.e., given
// inorder and postorder sequences forming a binary tree.
struct Node* constructTree(int inorder[], int postorder[], int n)
{
    // `pIndex` stores the index of the next unprocessed node from the end
    // of the postorder sequence
    int *pIndex = &n;
    return construct(inorder, 0, n, postorder, pIndex);
}
 
int main(void)
{
    /* Construct the following tree
               1
             /   \
            /     \
           2       3
          /       / \
         /       /   \
        4       5     6
               / \
              /   \
             7     8
    */
 
    int inorder[]    = { 4, 2, 1, 7, 5, 8, 3, 6 };
    int postorder[] = { 4, 2, 7, 8, 5, 6, 3, 1 };
    int n = sizeof(inorder)/sizeof(inorder[0]);
 
    struct Node* root = constructTree(inorder, postorder, n - 1);
 
    // traverse the constructed tree
    printf("Inorder traversal is "); inorderTraversal(root);
    printf("\nPostorder traversal is "); postorderTraversal(root);
 
    return 0;
}

Output:

Inorder traversal is 4 2 1 7 5 8 3 6 
Postorder traversal is 4 2 7 8 5 6 3 1