Im wondering could you help me to solvefilleach questionmeth

7. (40 pts) Answer the following questions on the binary tree node class given below. template class BTNode public: // members 8 BTNode parent; BTNode* left; BTNode* right; E data /I given methods BTNode () parent left right NULL; bool hasLeft ) return left-NULL bool hasRight() { return right != NULL; } bool isLeaf)return left--NULL&& right--NULL;) bool isRoot() return parentNULL; BTNode* connectLeft(BTNode* n) { left n; n->parent this; return n;} BTNode connectRight (BTNode n) right n; n->parent this; return n;) int getletBranchHeight() { return hasLeft() ? left->getHeight() + 1 : 0; } int getRightBranchheight() { return hasRight() ? right->getHeight() + 1 : 8; } int getHeight) return max (getLeftBranchHeight), getRightBranchHeight)); // methods to be filled int getSize) int getDiameter(); void levelOrder(vector& V); BTNode findMin(); bool isNorma1Node); bool isNormalTree BTNode* normalizeTree (1) (5 pts) Complete the following method which returns the size of subtree rooted at this node. int getsize) f (2) (7 pts) Diameter of a tree is the longest path in the tree. Complete the following method which returns the diameter of subtree rooted at this node. int getDiamter)

Solution

1>

int getSize(Node this) {
if (this == null) return(0);
else {
return(getSize(this.left) + 1 + getSize(this.right));
}
}

2>

int diameter(struct node * this)
{
/* when tree is empty */
if (this == 0)
return 0;

/* get the height of left and right sub-trees */
int l_height = height(this->left);
int r_height = height(this->right);

/* get the diameter of left and right sub-trees */
int l_diameter = diameter(this->left);
int r_diameter = diameter(this->right);

/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return max(l_height + r_height + 1, max(l_diameter, r_diameter));
}