Question

Create a (partial) BST class and a driver program to test it. The tree node will store integers as the data/key field (single field). Note that you will need to guarantee there are no duplicates in your insert function (the tree should refuse to insert a duplicate key). Call your files “tree.h”, “tree.cpp” and “main.cpp”. In addition, draw a picture of your tree (see note about random values below)

Public methods to include:

• Constructor
• Copy Constructor
• Overloaded Assignment Operator
• Destructor
• Insert value (do not add duplicate values)
• Find key – returns bool indicating if value is present in tree
• Print ancestors – prints a list of all values on the path to the given value
• Find height – returns integer
• Post-Order Traversal done recursively (print key values to screen)
• In-Order Traversal done iteratively (print key values to screen) (use STL Stack for this – see instructions on Canvas course site)
• Count leaves – returns number of leaves in tree Count full nodes – returns number of full nodes (nodes with two children) in tree

There will be additional private helper methods needed. The only methods that may print to the screen are the two traversals and the print ancestors.

Your driver should insert a minimum of 25 random* values to the tree. Test all the public methods of your class in the driver, printing the results to the screen. The user interface should clearly explain what is being tested and what results are expected.

*Random doesn’t mean you need to use the random number generator, though you are welcome to do so. But it does mean you do not want to insert values 1 thru 20 (in that order) into your tree (why not?). Consequently, you should decide on your values in advance and store them (in an array??) to insert. Include at least one duplicate value to properly test the insert.

Answer 1

1. Insert node and print Inorder Traversal : #include <iostream> using namespace std; class BST {     int data;     BST *left, *right;     public:     BST();     BST(int);           // Insert function.     BST* Insert(BST *, int);           // Inorder traversal.     void Inorder(BST *); }; BST :: BST() : data(0), left(NULL), right(NULL){} BST :: BST(int value) {     data = value;     left = right = NULL; } BST* BST :: Insert(BST *root, int value) {     if(!root)     {      // if root NULL then insert node.         return new BST(value);     }     // Insert data.     if(value > root->data)     {         root->right = Insert(root->right, value);     }     else     { root->left = Insert(root->left, value);     }     return root; } void BST :: Inorder(BST *root) {     if(!root)     {         return;     }     Inorder(root->left);     cout << root->data << endl;     Inorder(root->right); } int main() {     BST b, *root = NULL;     root = b.Insert(root, 50);     b.Insert(root, 30);     b.Insert(root, 20);     b.Insert(root, 40);     b.Insert(root, 70);     b.Insert(root, 60);     b.Insert(root, 80);     b.Inorder(root);     return 0; } 2. Find key: #include <iostream> using namespace std; // Binary tree node struct Node {     int data;     struct Node *left, *right;     Node(int data)     {         this->data = data;         left = right = NULL;     } }; bool ifNodeExists(struct Node* node, int key) {     if (node == NULL)         return false;     if (node->data == key)         return true;     /* then recur on left sutree */     bool res1 = ifNodeExists(node->left, key);     // node found     if(res1) return true;    //node not prsent at left side     bool res2 = ifNodeExists(node->right, key);     return res2; } // Driver Code int main() {     struct Node* root = new Node(0);     root->left = new Node(1);     root->left->left = new Node(3);     root->left->left->left = new Node(17);     root->left->right = new Node(4);     root->left->right->left = new Node(8);     root->left->right->right = new Node(90);     root->right = new Node(2);     root->right->left = new Node(5);     root->right->right = new Node(6);     int key = 4;     if (ifNodeExists(root, key))         cout << "YES";     else         cout << "NO";     return 0; } 3. count no. of leaf node in tree: #include <bits/stdc++.h> using namespace std; struct node {     int data;     struct node* left;     struct node* right; }; unsigned int getLeafCount(struct node* node) {     if(node == NULL)              return 0;     if(node->left == NULL && node->right == NULL)         return 1;              else         return getLeafCount(node->left)+             getLeafCount(node->right); } struct node* newNode(int data) {     struct node* node = (struct node*)                     malloc(sizeof(struct node));     node->data = data;     node->left = NULL;     node->right = NULL;       return(node); } int main() {     /*create a tree*/     struct node *root = newNode(1);     root->left = newNode(12);     root->right = newNode(13);     root->left->left = newNode(40);     root->left->right = newNode(75);       cout << "No. of leaf node: "<<                 getLeafCount(root) << endl; return 0; } 4. To calculate height of tree: #include <bits/stdc++.h> using namespace std; class node {     public:     int data;     node* left;     node* right; }; int maxDepth(node* node) {     if (node == NULL)         return 0;     else     {         int lDepth = maxDepth(node->left);         int rDepth = maxDepth(node->right);                 if (lDepth > rDepth)             return(lDepth + 1);         else return(rDepth + 1);     } } node* newNode(int data) {     node* Node = new node();     Node->data = data;     Node->left = NULL;     Node->right = NULL;           return(Node); }    int main() {     node *root = newNode(1); root->left = newNode(2);     root->right = newNode(3);     root->left->left = newNode(4);     root->left->right = newNode(5);           cout << "Height of tree is " << maxDepth(root);     return 0; }