4.0.0 Full Binary Tree Theory & Properties

A Full Binary Tree is strictly defined as a tree where every node has exactly 0 or exactly 2 children.
Property 1: A full binary tree with I internal nodes will mathematically always have I + 1 leaf nodes.
Property 2: The total number of nodes in a Full Binary Tree is equal to 2I + 1.

4.0.1 isFullBinaryTree Logic

int isFullBinaryTree(struct node* root){
int left, right;
if (root == NULL)
return 1;
if (root->left == NULL && root->right == NULL)
return 1;
else if (root->left && root->right) {
left = isFullBinaryTree(root->left);
right = isFullBinaryTree(root->right);
return (left && right);
}
return 0;
}

4.0.2 Main Driver

int main(){
struct node* root = createNode(10);
root->left = createNode(20);
root->right = createNode(30);
root->left->left = createNode(40);
root->left->right = createNode(50);
printf("root is %d\n", root->data);
printf("Left node is %d\n", root->left->data);
printf("right node is %d\n", root->right->data);
if(isFullBinaryTree(root))
printf("FULL Binary tree");
else{
printf("NOT a FULL Binary tree");
}
return 0;
}

4.0.3 Full FBT Code

struct node {
struct node * left;
int data;
struct node * right;
};

struct node* createNode(int data){
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

int isFullBinaryTree(struct node* root){
int left, right;
if (root == NULL)
return 1;
if (root->left == NULL && root->right == NULL)
return 1;
else if (root->left && root->right) {
left = isFullBinaryTree(root->left);
right = isFullBinaryTree(root->right);
return (left && right);
}
return 0;
}

int main(){
struct node* root = createNode(10);
root->left = createNode(20);
root->right = createNode(30);
root->left->left = createNode(40);
root->left->right = createNode(50);
printf("root is %d\n", root->data);
printf("Left node is %d\n", root->left->data);
printf("right node is %d\n", root->right->data);
if(isFullBinaryTree(root))
printf("FULL Binary tree");
else{
printf("NOT a FULL Binary tree");
}
return 0;
}

Logical Breakdown

Click the ➔ arrow on any line to reveal the underlying logic here.