For such queries, first thing is write down your valid conditions and then write code for those conditions.
For your query, whether a binary tree is a full can be determined by:
- If a binary tree node is NULL
- If a binary tree node does have empty left and right sub-trees
- If a binary tree node has left and right sub-trees, then it is a part of a full binary tree by definition. Recursively, check if the left and right sub-trees are also binary trees themselves.
In all other combinations of right and left sub-trees, the binary tree is not a full binary tree.
Thus, coding above in a function would look like:
bool isFullTree (struct Node* root)
{
if (root == NULL)
return true;
if (root->left == NULL && root->right == NULL)
return true;
if ((root->left) && (root->right))
return (isFullTree(root->left) && isFullTree(root->right));
return false;
}
Quote:
can we allocate memory the size of a treenode structure
That is not needed for figuring out if full or not. while creating tree you have already allocated space for each node. You just need to pass the tree as shared above to find if full or not.