A binary tree has FullShape if every triple either has two e

A binary tree has FullShape if every triple either has two empty subtrees or has two triple subtrees. Every node is a leaf or a full node. Complete this recursive pseudo code function that returns true just if tree has FullShape. Boolean hasFullShape (tree)

Solution

Boolean hasFullShape (root, index, numberofnodes)

       Input: root ,node index, and number of nodes

       Output: Boolean value true if tree has full shape

    // An empty tree is HasFullShape

    if (root == NULL)

        Return true;

/*If index assigned to current node is more than number of nodes in tree, then tree is not in full shape*/

if (index >= numberofnodes)

        Return false;

    /*Recursion for left and right subtree*/

return (hasFullShape(root->left, 2*index + 1, number_nodes) && hasFullShape(root->right, 2*index + 2, number_nodes));