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.

 

postorder 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

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[0]);

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