Construct Tree From Given Inorder and Preorder traversals in C

Construct Tree From Given Inorder and Preorder 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.

Preorder Traversal: We first print the node, then move to the left subtree and the right subtree.
Inorder Traversal: We first move to the left subtree, then print the node and move to the right subtree.

inorder preorder traversal in C

Algorithm :

 

  • Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick the next element in the next recursive call.
  • Create a new tree node tNode with the data as the picked element. 
  • Find the picked element’s index in Inorder. Let the index be inIndex. 
  • Call buildTree for elements before inIndex and make the built tree as a left subtree of tNode. 
  • Call buildTree for elements after inIndex and make the built tree as a right subtree of tNode.
  • return tNode.
tree from inorder and preorder traversal in C

C Program based on above Algorithm

#include <stdio.h>
#include <stdlib.h>

struct node {
char data;
struct node* left;
struct node* right;
};

int search(char arr[], int strt, int end, char value);
struct node* newNode(char data);

struct node* buildTree(char in[], char pre[], int inStrt, int inEnd)
{
static int preIndex = 0;

if (inStrt > inEnd)
return NULL;

struct node* tNode = newNode(pre[preIndex++]);

if (inStrt == inEnd)
return tNode;

int inIndex = search(in, inStrt, inEnd, tNode->data);

tNode->left = buildTree(in, pre, inStrt, inIndex - 1);
tNode->right = buildTree(in, pre, inIndex + 1, inEnd);

return tNode;
}

int search(char arr[], int strt, int end, char value)
{
int i;
for (i = strt; i <= end; i++) {
if (arr[i] == value)
return i;
}
}

struct node* newNode(char data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

void printInorder(struct node* node)
{
if (node == NULL)
return;

printInorder(node->left);

printf("%c ", node->data);

printInorder(node->right);
}

int main()
{
char in[] = { 'D', 'B', 'E', 'A', 'F', 'C' };
char pre[] = { 'A', 'B', 'D', 'E', 'C', 'F' };
int len = sizeof(in) / sizeof(in[0]);
struct node* root = buildTree(in, pre, 0, len - 1);

printf("Inorder traversal of the constructed tree is \n");
printInorder(root);
getchar();
}
Output:
Inorder traversal of the constructed tree is D B E A F C