Question

Write a C function with signature btbstree (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 btreenode { struct btreenode *left; int data; struct btreenode *right; |}bt;

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

//required method

bt *bstree(int* post, int size){

                if(size==0){

                                return NULL; //empty bst

                }

                //in a post order traversal, root value will always be at the end.

                //so we create a node with data=last value in the array, this node

                //will be the root node

                bt* root=(bt*) malloc(sizeof(bt*));

                root->data=post[size-1];

                root->left=NULL;

                root->right=NULL;          

                //looping through each remaining values in the array, from last to first

                for(int i=size-2;i>=0;i--){

                                //fetching current value

                                int value=post[i];

                                //creating a new node with this value

                                bt* newnode=(bt*) malloc(sizeof(bt*));

                                newnode->data=value;

                                newnode->left=NULL;

                                newnode->right=NULL;

                               

                                //taking reference to root

                                bt* node=root;

                                //a flag to control below loop

                                int added=0;

                                //looping until newnode is added in proper place

                                while(added==0){

                                                //if value is bigger than node's data, moving to right subtree

                                                if(value>node->data){

                                                                //if there is no right node, adding newnode as right node

                                                                if(node->right==NULL){

                                                                                node->right=newnode;

                                                                                added=1; //loop will end

                                                                }else{

                                                                                //otherwise moving to right subtree

                                                                                node=node->right;

                                                                }

                                                }else{

                                                                //if value is smaller than node's value, moving to left subtree,

                                                                //and adding to appropriate position

                                                                if(node->left==NULL){

                                                                                node->left=newnode;

                                                                                added=1; //loop will end

                                                                }else{

                                                                                node=node->left;

                                                                }

                                                }

                                }             

                }

                //returning the reference to the root

                return root;

}