Check whether a binary tree is a full binary tree in C++

In this tutorial, I will show how to check whether a given binary tree is a full binary tree or not in C++. To implement this, we need to have a clear understanding of how to use trees with data structures in c++. Let us get started.

Check if a Binary Tree is a Full Binary Tree in C++

A binary tree is a tree that can, at most, have 2 children. So following, a Full Binary Tree is one in which there are either both the children present or neither of them. In simple words, a node cannot have a single child. I will show an example:

Binary Tree:


                       70                Since all the nodes have both children or neither of them, 

                  /         \            this is a full binary tree.     

              20              50

           /      \         /      \

        10         30     40        60

I will be using structures and pointers in c++ to implement my approach. First I have defined the structure of the node and then the AddNode() takes root value and adds nodes. Apart from this, I have two more functions: check() and main() function.

The check() function takes the root node as a parameter and checks the different validation conditions. Basically, I have to check for three conditions:

  • if there is no root node i.e. the tree is empty.
  • when the root node has neither left child nor right child.
  • if the root node has both the left child and right child, then the function needs to be called recursively and the respective left subtree and right subtree need to be checked.

In the main() function, I have added all the nodes and their children. The check() function is called by passing the root node. I have used an integer variable to store the value returned from our function check(). If the value is 1, then it is a full binary tree. Otherwise, it is not a full binary tree.

I have shown my code below:

#include <iostream>
using namespace std;

//basic structure of binary tree
struct node
{
    int key;
    struct node *leftNode, *rightNode;
};

struct node *AddNode(char k)
{
    struct node *Node = new node;
    Node->key = k;
    Node->leftNode = Node->rightNode = NULL;
    return Node;
}

int check(struct node *root)
{
    //if no node, full binary tree
    if(root == NULL)
    {
        return 1;
    }

    //if the node has neither left child nor right child, full binary tree 
    if(root->leftNode == NULL && root->rightNode == NULL)
    {
        return 1;
    }

    //if both the children are there, again call check function with new roots
    if((root->leftNode) && (root->rightNode))
    {
        return (check(root->leftNode) && check(root->rightNode));
    }

    return 0;
}

int main()
{
    struct node *root = NULL;
    root = AddNode(70);

    root->leftNode = AddNode(20);
    root->rightNode = AddNode(50);

    root->leftNode->rightNode = AddNode(10);
    root->leftNode->leftNode = AddNode(30);
    root->rightNode->leftNode = AddNode(40);
    root->rightNode->rightNode = AddNode(60);

    int flag = check(root);

    if(flag == 1)
    {
        cout << "Full Binary Tree" << endl;
    }
    else
    {
        cout << "Not a Full Binary Tree" << endl;
    }

    return 0;
    
}

Input:

I have entered the root node, then its left and right child, and then one another level with all the children. (similar to the example explained earlier).

Output:

Full Binary Tree

Also read: Reverse Level Order Traversal of Binary Tree in C++

Leave a Reply

Your email address will not be published. Required fields are marked *