Question

Can you complete the tasks inside the sample code. All the to-do task is inside the code commented out.

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


typedef struct TreeNode {
        int val; 
        struct TreeNode *left; 
        struct TreeNode *right; 
}node; 

/*Task 1 - Complete the function below,
  newNode() will return a tree node*/
node* newNode(int key){
        
}

/*Task 2 - Complete the function below to return
the size (number of elements stored) of a binary 
tree*/
int size(node* root){
         
 
}


/*Task 3 - Complete the function below to print 
a binary tree while performing an Preorder traversal.
Recall preorder traversal: 
        visit parent
        visit left subtree
        visit right subtree
you MUST use recursion  */

void printPreorder(node* r){
        
}


/*Task 4 - Complete the function below to print 
a binary tree while performing an Inorder traversal.
Recall inorder traversal: 
        visit left subtree
        visit parent
        visit right subtree
you MUST use recursion  */

void printInorder(node* r){
        
}



/*
  Task 5 - Complete the function below to clear a 
  binary tree. Perform a recursive traversal of a
  tree destroying all nodes.
*/

void clearTree(node* root){

}

/*
  Task 6 - Complete the function below to find and
  return the max depth of a binary tree. 
  Recall that max depth of a tree is the number of 
  nodes along the longest path from the root node 
  down to the farthest leaf node.
*/
int maxDepth (node* root){

}

/*
  Task 7 - Complete the function below to create 
  an ordered binary tree (bst). In a binary search 
  tree, for every node, all nodes in the left subtree
  are smaller while all nodes in the right subtree are
  larger. (You should compare the key with current value
  then decide whether to move to the left or right subtree)
*/

node* insertBST(node* root, int key) 
{ 
    
   
} 



int main(int argc, char const *argv[])
{

        node *root = newNode(5); 
        root->left = newNode(4);
        root->right = newNode(12); 
        root->right->left = newNode(13);
        root->right->right = newNode(2);
        root->left->left = newNode(8);


        printf("Size of the tree is %d\n",size(root));
        printf("Maximum depth of the tree is %d\n", maxDepth(root) );
        printPreorder(root); 
        printf("\n");
        printInorder(root); 
        printf("\n");

        node* bst; 
        int input ; 
        scanf("%d", &input); 
        while(input != -999){
                bst = insertBST(bst, input); 
                scanf("%d", &input); 
        }

        printInorder(bst);
        
        return 0;
}

Answer 1

Note: here all function done with comment after every logic applied for easy understanding still if you have any error feel free to ask me or post the issue.

Main.c

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


typedef struct TreeNode {
        int val; 
        struct TreeNode *left; 
        struct TreeNode *right; 
}node; 

node* newNode(int key){
    
      // allocate memory to node neewNode using malloc 
        node *newNode = (node*) malloc(sizeof(node));
        newNode->val = key;
        newNode->left = NULL;
        newNode->right = NULL;
        
        return newNode;
}

int size(node* root){
    int count = 1;
    
    // if left is not null goto left node and increment count
    if (root->left != NULL) {
       count += size(root->left);
    }
    
    // if right is not null goto left node and increment count
    if (root->right != NULL) {
        count += size(root->right);
    }
    
    return count;
}

void printPreorder(node* r){
        if(r == NULL)
             return;
             
        printf("%d ",r->val);
        printPreorder(r->left);
        printPreorder(r->right);
}

void printInorder(node* r){
        if(r == NULL)
             return;
             
        printPreorder(r->left);
        printf("%d ",r->val);
        printPreorder(r->right);
}

void clearTree(node* root){
        if(root == NULL)
           return;
        clearTree(root->left);
        clearTree(root->right);
        
        // it will free each node memory of the tree and make it danglic pointer
        free(root);
}

int maxDepth (node* root){
     if(root == NULL)
             return 0;
    
    else { 
       // compute the depth of each subtree 
       int lDepth = maxDepth(root->left); 
       int rDepth = maxDepth(root->right); 
  
       // return  the max depth 
       if (lDepth > rDepth)  
           return(lDepth+1); 
       else return(rDepth+1); 
   }
}

node* insertBST(node* root, int key) 
{ 
   // If the tree is empty, return a new node 
    if (root == NULL) {
       return newNode(key); 
   }
  
    // if key is less than current node val
    if (key < root->val) 
        root->left  = insertBST(root->left, key); 
        
    // else if key is greater than current node val
    else if (key > root->val) 
        root->right = insertBST(root->right, key);    
  
    // return the (unchanged) node pointer 
    return root; 
} 



int main(int argc, char const *argv[])
{
        node *root = newNode(5); 
        root->left = newNode(4);
        root->right = newNode(12); 
        root->right->left = newNode(13);
        root->right->right = newNode(2);
        root->left->left = newNode(8);


        printf("Size of the tree is %d\n",size(root));
        printf("Maximum depth of the tree is %d\n", maxDepth(root) );
        printPreorder(root); 
        printf("\n");
        printInorder(root); 
        printf("\n");

       // intialise bst with NULL
        node* bst = NULL; 
        int input ; 
        printf("Enter key for making BST (if enter -999 stop)\n");
        scanf("%d", &input); 
        while(input != -999){
                bst = insertBST(bst, input); 
                scanf("%d", &input); 
        }

        printInorder(bst);
        
        return 0;
}