Question

**Bonus Question Write a C function with signature bt' bstree (int' post, int size) that gets the post-order traversal of a binary search tree in the form of an int array,reconstructs the tree and returns a pointer to the tree root as output (The second input parameter size specifies the number of elements in the tree). Note: Type bt is defined in the following way: typedef struct btreenodel struct btreenode *left; int data; struct btreenode *right; }bt; 12pt Paragraph B I U ATv | :

Answer 1

C code for above problem

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

typedef struct btreenode
{
   int data;
   struct btreenode *left,*right;
}bt;

int post_index=0;

// comparator that is used to sort the array
int comparator(const void *a, const void *b)
{
   return (*(int*)a-*(int*)b);
}

// function that creates a new node and returns it
bt * create_node(int data)
{
   bt *root=(bt *)malloc(sizeof(bt));
   root->data=data;
   root->left=NULL;
   root->right=NULL;
   return root;
}

// function that creates a tree using given postorder and returns the root
bt * create_tree(int *in,int *post,int start,int end)
{
   if(start>end || post_index<0)
       return NULL;
   int value=post[post_index--];
   int ind=-1;
   for(int i=start;i<=end;i++)
   {
       if(in[i]==value)
       {
           ind=i;
           break;
       }
   }
   bt *root=create_node(value);
   root->right=create_tree(in,post,ind+1,end);
   root->left=create_tree(in,post,start,ind-1);
   return root;
}

// function that returns the tree that is equivalent to give postorder
bt * bstree(int *post,int size)
{
   int in[size];
   for(int i=0;i<size;i++)
       in[i]=post[i];
   qsort(in,size,sizeof(int),comparator);
   post_index=size-1;
   return create_tree(in,post,0,size-1);
}

// function that prints the tree in post order
void postorder(bt *root)
{
   if(!root)
       return;
   postorder(root->left);
   postorder(root->right);
   printf("%d ",root->data);
}

// testing main method
int main()
{
   int post[]={1,3,2,5,7,6,4};
   int size=sizeof(post)/sizeof(int);
   bt *root=bstree(post,size);
   printf("Post order Traversal: ");
   postorder(root);
   printf("\n");
   return 0;
}

Sample output

Post order Traversal: 1 3 2 5 7 6 4

Given post order and tree's post order traversal looks same.

Mention in comments if any mistakes or errors are found. Thank you.