Question

C++ ONLY

This question has 2 parts (a, and b).

The partial definition of tree with up to 3-nodes for each node is given below. This is not a binary search tree!

class Tree3 {

public :

Tree3() {}

private :

class Node {

public :

int Val ;
Node * Left ; Node * Middle ; Node * Right ;

};

}; Node * Root { nullptr };

a) A Node is considered balanced if the sum of the all the nodes on the Left side of the node is equal to the sum of all the nodes on the Right side of the node. The values of nodes in the Middle are ignored.

A Tree3 is considered balanced if the root node is balanced.
Implement the function Tree3:: isBalanced . Implement any helper functions as needed.

bool Tree3:: isBalanced() const

b) What is the tight bound runtime complexity of isBalanced , i.e. big-Theta ? of isBalanced . Write your reasoning in one sentence.

Answer 1

a)

int sum(Node *root) { if(root == NULL) return 0; return sum(root->Left) + root->Val + sum(root->Right); } int isBalanced(Node* node) { int ls, rs; if(node == NULL || (node->Left == NULL && node->Right == NULL)) return 1; ls = sum(node->left); rs = sum(node->right); if((node->Val == ls + rs)&& isBalanced(node->Left) && isBalanced(node->Right)) return 1; return 0; } 

b)

Time Complexity: theta(n^2) in worst case. Worst case occurs for a skewed tree. In this case, one recursion is required to find the sum of each node, and the outer recursion is used to identify if the tree is balanced or not.