*** NEED THE CODE IN C ***

/* * Your task is to implement 'levelsum' * which returns the sum of all the nodes at a particular level in * the binary tree 'root' */ #include  #include  struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; int isbst(struct TreeNode * root); struct TreeNode * createTreeNode(int val); void destroyTree(struct TreeNode * node); void displayTree(struct TreeNode * node); void displayTreeNode(struct TreeNode * node); struct TreeNode * buildTree1(); struct TreeNode * buildTree2(); void displayInorder(struct TreeNode * root); void displayPreorder(struct TreeNode * root); int treeSize(struct TreeNode * root); void main() { struct TreeNode * root = buildTree1(); printf("Tree 1: "); printf("Inorder: "); displayInorder(root); printf(" "); printf("Preorder: "); displayPreorder(root); printf(" "); printf("Tree size: %d ", treeSize(root)); if (isbst(root)==1) { printf("It's a binary search tree "); } else { printf("It's not a binary search tree "); } destroyTree(root); printf(" "); root = buildTree2(); printf("Tree 2: "); printf("Inorder: "); displayInorder(root); printf(" "); printf("Preorder: "); displayPreorder(root); printf(" "); printf("Tree size: %d ", treeSize(root)); if (isbst(root)==1) { printf("It's a binary search tree "); } else { printf("It's not a binary search tree "); } destroyTree(root); } int isbst(struct TreeNode * root) { return 1; } int treeSize(struct TreeNode *root) { if (root==NULL) { return 0; } return 1+ treeSize(root->left) + treeSize(root->right); } struct TreeNode * createTreeNode(int val) { struct TreeNode * node = (struct TreeNode *) malloc(sizeof(struct TreeNode)); node->val = val; node->left = NULL; node->right = NULL; return node; } void destroyTree(struct TreeNode * node) { if (node == NULL) { return; } destroyTree(node->left); destroyTree(node->right); free(node); } void displayTreeNode(struct TreeNode * node) { printf("%d", node->val); } struct TreeNode * buildTree1() { struct TreeNode *p8 = createTreeNode(8); struct TreeNode *p4 = createTreeNode(4); struct TreeNode *p15 = createTreeNode(15); struct TreeNode *p1 = createTreeNode(1); struct TreeNode *p6 = createTreeNode(6); struct TreeNode *p13 = createTreeNode(13); struct TreeNode *p5 = createTreeNode(5); struct TreeNode *p7 = createTreeNode(7); struct TreeNode *p14 = createTreeNode(14); p8->left=p4; p8->right=p15; p4->left=p1; p4->right=p6; p6->left=p5; p6->right=p7; p15->left=p13; p13->right=p14; return p8; } struct TreeNode * buildTree2() { struct TreeNode *p8 = createTreeNode(8); struct TreeNode *p4 = createTreeNode(4); struct TreeNode *p15 = createTreeNode(15); struct TreeNode *p1 = createTreeNode(1); struct TreeNode *p9 = createTreeNode(9); struct TreeNode *p13 = createTreeNode(13); struct TreeNode *p5 = createTreeNode(5); struct TreeNode *p11 = createTreeNode(11); struct TreeNode *p14 = createTreeNode(14); p8->left=p4; p8->right=p15; p4->left=p1; p4->right=p9; p15->left=p13; p9->left=p5; p9->right=p11; p13->right=p14; return p8; } void displayInorder(struct TreeNode * root) { if (root == NULL) return; displayInorder(root->left); displayTreeNode(root); printf(" "); displayInorder(root->right); } void displayPreorder(struct TreeNode * root) { if (root == NULL) return; displayTreeNode(root); printf(" "); displayPreorder(root->left); displayPreorder(root->right); } 

Problem 2 (2 pt). Attached is a program isbst.c which has a function intisbst(structNoderoot) that 1 if the binary tree rooted at "root" is a binary search tree, and 0 otherwise. Unfortunately, the function doesn't work. Rewrite it (and possibly add other functions) so that it works, - The time complexity of your algorithm should be O(n), where n is the number of nodes in the tree. - The space complexity of your algorithm should be O(n) too. You can use the following helper function to determine the size of the tree: - int sizetree(struct Node * root): returns the number of nodes in the tree It has time complexity O(n) and space complexity O(n) (The worst case space complexity comes from the stack for a very unbalanced tree.) Note: The test cases for the program shown below, but your algorithm should work for any tree. The program uses the following binary search trees for testing. It's a binary search tree: It's not a binary search tree: 9 is out of place