C++:

Implement the insert(V x) method-

The tree should be sorted, the values of left subtree are smaller than the root; the values of the right subtree are larger than the root

treenode.h(given)

#include #include #include using namespace std;

template class TreeNode{ T datum; TreeNode* left, * right; public: // constructor with datum value, left and right are nullptr TreeNode(T x){ datum=x; left = nullptr; right = nullptr; } // constructor with datum value, left and right values TreeNode(T x, TreeNode* lft, TreeNode* rgt){ datum = x; left = lft; right = rgt; } //destructor releases left and right nodes, if not nullptr ~TreeNode(){ if (left) { delete left; } if (right) { delete right; } } // get datum value T getDatum(){ return datum; } // get left pointer TreeNode* getLeft(){ return left; } // get right pointer TreeNode* getRight(){ return right; } // set the left pointer void setLeft(TreeNode* p){ left = p; } // set the right pointer void setRight(TreeNode* p){ right = p; } };

tree.h (implement insert method here)

#include "treeNode.h" #include

template class tree { TreeNode * root; int size; public: // default constructor // by default, the tree is empty tree(){ root = nullptr; size = 0; }

// search value x in tree rooted at node t bool treeSearch(V x, TreeNode* t){ if(t == nullptr) return false; if(t->getDatum() == x) return true; return treeSearch(x, t->getLeft()) || treeSearch(x, t->getRight()); } bool treeSearch(V x){ treeSearch(x, root); }

// binary search value x in tree rooted at node t bool treeBSearch(V x, TreeNode* t){ if(t == nullptr) return false; if(t->getDatum() == x) return true; if(t->getDatum() > x) return treeBSearch(x, t->getLeft()); else return treeBSearch(x, t->getRight()); } bool treeBSearch(V x){ return treeBSearch(x, root); } // check node t is leaf bool isLeaf(TreeNode* t){ return t!= nullptr && t->getLeft() == nullptr && t->getRight() == nullptr; //implement this method //return t!= nullptr && t->getLeft() == nullptr && t->getRight() == nullptr; } // find the height of the tree rooted at node t int height(TreeNode* t){ //implement this method if(t == nullptr) return -1; if(isLeaf(t)) return 0; return 1 + std::max(height(t->getLeft()),height(t->getRight())); } int height(){ return height(root); } // find the number of nodes of tree rooted at t int nNodes(TreeNode* t){ if(t == nullptr) return 0; return 1 + nNode(t->getLeft() + nNode(t->getRight())); } int nNodes(){ return nNodes(root); }

// insert value x to the current tree object void insert(V x){ ~~~~~~~~~~ }