Click here to Skip to main content
15,867,686 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
my typedef structure is,
C
    typedef struct treenode{
        int data;
        struct treenode *left, *right;
    } *binarytree;

What I have tried:

I was told this was similar to writing a stack program so I tried editing my stack program, but I'm unsure if this is correct do to the instruction being vague.
Posted
Updated 23-Nov-22 12:40pm
v6

1 solution

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:
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.
 
Share this answer
 
Comments
CPallini 23-Nov-22 2:27am    
5.
Sandeep Mewara 23-Nov-22 2:30am    
Thanks! BTW, you missed 5 :)
CPallini 23-Nov-22 2:41am    
(Sorry) Fixed now.
Sandeep Mewara 23-Nov-22 3:06am    
:thumbsup:

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900