Full Binary Tree: Types, Properties, and Program in C
A full binary tree or proper binary tree in which all the nodes have zero or two children. In this article, we will briefly discuss all full binary tree, its properties, example, and finally a c program to check whether the given binary tree is a full binary tree or not.
Binary tree in data structure has numerous types, and one of its most important types is the full binary tree. A binary tree has either zero, one, or two child nodes but not more than two. The full binary tree is a type of binary tree; other types of binary trees include:
- A Complete binary tree.
- Balanced binary tree (AVL tree, Red black tree, etc.).
- Skewed binary tree (left-skewed tree, right-skewed tree).
- Degenerate binary tree.
A full binary tree is such a binary tree whose all nodes have either zero or two child, meaning a tree with one child node will not be considered a full binary tree. In this article, we will learn the full binary tree, its properties, and the algorithm.
Best-suited IT & Software courses for you
Learn IT & Software with these high-rated online courses
What is Full Binary Tree?
A full binary tree is a full-fledged binary tree with few conditions, like a full binary tree, which should have either zero or two children only; if any node has one child node, then it would not be considered a full binary tree. A full binary tree is also known as a Proper binary tree.
Some important terms related to the Full binary tree:
- Root node: The root node does not have any edge coming towards it or any parent node.
- Child node: The node having some incoming edge.
- Internal/External node: non-leaf nodes are internal nodes, and leaf nodes are external nodes.
- Sibling: Two or more nodes having the same parent node.
- Height: Total number of edges from that node to the root node.
- Level: Number of nodes in the path from that node to the root node.
- Degree: A degree of any node is calculated by counting the number of child nodes of that particular node.
Also Read: Types of Binary Tree
Also Read: Tree Traversal in Data Structure
Properties of Full Binary Tree
Before discussing the properties of the full binary tree, let’s understand the notations of some basic terms; in this article, we will be using
i for the total number of internal nodes.
n for the total number of nodes.
l for a number of leaves.
h for the number of levels.
The properties of the full binary tree are as follows:
- The total number of nodes is 2i +1 or 2l -1.
- The total number of internal nodes is (n-1)/2 or l – 1.
- A full binary tree has i +1 or 2l – 1 number of total leaves.
- A binary tree can have at most 2h -1.
Also Read: All about Balanced Binary Tree
Also Read: Splitting in Decision Tree
Example of Binary Tree
1
2
The above two diagrams are examples of the full binary tree.
Program for Full Binary Tree
Here is the code to check whether the given binary tree is a Full binary tree or not.
int main() { struct Node *root = NULL; root = createNewNode(25); root → left = createNewNode(15); root → right = createNewNode(30);
root → left →left = createNewNode(10); root → left →right = createNewNode(20); root → left → left → left = createNewNode(6); root → left → left → right = createNewNode(12);
root → right →left = createNewNode(28); root → right →right = createNewNode(35);
if (isFullBinaryTree(root)) printf("The given tree is a full binary tree\n"); else printf("The given tree is not a full binary tree\n");}
#include \n \n <stdio.h>\n \n \n \n \n \n struct Node {\n \n int item;\n \n struct Node *left, *right;\n \n };\n \n \n \n struct Node *createNewNode(char a) {\n \n struct Node *node = (struct Node *)malloc(sizeof(struct Node));\n \n node → item = a;\n \n node → right = node → left = NULL;\n \n return node;\n \n }\n \n \n \n bool isFullBinaryTree(struct Node *root) {\n \n if (root == NULL)\n \n return true;\n \n \n \n \n \n if (root → left == NULL && root → right == NULL)\n \n return true;\n \n \n \n if ((root → left) && (root → right))\n \n return (isFullBinaryTree(root → left) && isFullBinaryTree(root → right));\n \n \n \n return false;\n \n }\n \n \n \n \n \n </stdio.h>
Also Read: Complete Binary Tree
Also Read: Red Black Tree
Conclusion
In this article, we have briefly discussed full binary tree, its types, properties, and program to check whether the given tree is a full binary tree or not.
Hope you will like the article.
Contributed By: Kanika Joshi
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
