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:

C++

/* This function tests if a binary tree is a full binary tree. */ bool isFullTree (struct Node* root) { // 1. If empty tree if (root == NULL) return true; // 2. If leaf node if (root->left == NULL && root->right == NULL) return true; // 3. If both left and right are not NULL, and left & right subtrees // are full (checking recursively) if ((root->left) && (root->right)) return (isFullTree(root->left) && isFullTree(root->right)); // If none of the above condition is true 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.