Fall 2016_CS301_2

Semester:      Fall 2016

Assignment No.  2 Semester: Fall 2016 CS301 – Data Structures

Total Marks: 20 Due Date: Tuesday, November 29, 2016

Instructions

Please read the following instructions carefully before submitting assignment:

It should be clear that your assignment will not get any credit if:

o        Assignment is submitted after due date.

o        Submitted assignment does not open or file is corrupt.

o        Assignment is copied (From internet/ to from students).

For clarity and simplicity, You are required to Upload/Submit only ONE .CPP file. Other format will not be accepted and will be graded zero marks.

Note: Use ONLY Dev-C++ IDE for writing and executing your code.

Objectives:

The purpose of this assignment is to make you familiar with following topics:

• Tree

• Binary Tree

• Terminologies of a Binary Tree

• Level

• Complete Binary Tree

• Level of a Complete Binary Tree

Assignment Submission Instructions

You have to submit only .cpp on the Assignments interface of CS301 at VULMS. Assignment submitted in any other format will not be accepted and will be graded zero marks.

Assignment :

Question 1:                   Marks= 20                                                                                                               

Write down C++ code to create a complete binary Tree in which user can add any number of node/elements (Numeric). After Creating a complete binary tree , You need to calculate the product of the 2^nd lowest level and find the smallest number in the binary tree as given in the example

Product of Elements in 2nd last level  (N-1)= 20

Smallest number in Binary Tree = 2

Note: N levels mean any number of levels.

Deadline:

Your assignment must be uploaded on or before Tuesday, November 29, 2016. We shall not accept your solution through email after the due date.

Solution File: Copy this code and paste in dev c++ then compile and run.

// A C++ program to find the deepest left leaf in a given binary tree #include <stdio.h> #include <iostream> using namespace std; struct Node { int val; struct Node *left, *right; }; Node *newNode(int data) { Node *temp = new Node; temp->val = data; temp->left = temp->right = NULL; return temp; } // A utility function to find deepest leaf node. // lvl: level of current node. // maxlvl: pointer to the deepest left leaf node found so far // isLeft: A bool indicate that this node is left child of its parent // resPtr: Pointer to the result void deepestLeftLeafUtil(Node *root, int lvl, int *maxlvl, bool isLeft, Node **resPtr) { // Base case if (root == NULL) return; // Update result if this node is left leaf and its level is more // than the maxl level of the current result if (isLeft && !root->left && !root->right && lvl > *maxlvl) { *resPtr = root; *maxlvl = lvl; return; } // Recur for left and right subtrees deepestLeftLeafUtil(root->left, lvl+1, maxlvl, true, resPtr); deepestLeftLeafUtil(root->right, lvl+1, maxlvl, false, resPtr); } // A wrapper over deepestLeftLeafUtil(). Node* deepestLeftLeaf(Node *root) { int maxlevel = 0; Node *result = NULL; deepestLeftLeafUtil(root, 0, &maxlevel, false, &result); return result; } Node* insert(Node* node, int val) { /* 1. If the tree is empty, return a new, single node */ if (node == NULL) return(newNode(val)); else { /* 2. Otherwise, recur down the tree */ if (val <= node->val) node->left = insert(node->left, val); else node->right = insert(node->right, val); /* return the (unchanged) node pointer */ return node; } } int minValue(Node* node) { Node* current = node; /* loop down to find the leftmost leaf */ while (current->left != NULL) { current = current->left; } return(current->val); } // Driver program to test above function int main() { int a, b, c, d, e, f, g, h, i, j; cout<<"Enter 10 Numbers in Tree:\n"; cin>>a>>b>>c>>d>>e>>f>>g>>h>>i>>j; Node* root = newNode(a); root->left = newNode(b); root->right = newNode(c); root->left->left = newNode(d); root->right->left = newNode(e); root->right->right = newNode(f); root->right->left->right = newNode(g); root->right->right->right = newNode(h); root->right->left->right->left = newNode(i); root->right->right->right->right = newNode(j); root = insert(root, a); insert(root, b); insert(root, c); insert(root, d); insert(root, e); insert(root, f); insert(root, g); insert(root, h); insert(root, i); insert(root, j); Node *result = deepestLeftLeaf(root); if (result){ cout << "Product of 2nd lowest level of a binary tree is: " << result->val * result->val; } else{ cout << "There is no left leaf in the given tree"; } printf("\nMinimum value in BST is %d", minValue(root)); return 0; }