Binary Tree: Given a binary tree, check if the tree is perfect or not.

Problem Statement:

You are given a binary tree, you need to check if it is a perfect binary tree or not.

A binary tree is considered as perfect binary tree if all the internal nodes have 2 children and all the leaves are at the same level.

Example:

Input:

Output:
True

Solution Explanation:

Idea is to perform a level order traversal of the binary tree using queue.

Then we check if all the internal nodes have 2 children and all are leaves at the same level.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

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


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}


bool solution(Node * root)
{
    if (root==NULL) 
    	return true;
    
    queue<Node*> q;
    q.push(root);

    int nodeCount = 1;
    
    while (!q.empty()) 
    {
        int size = q.size();

        if (size != nodeCount) 
        	return false;
        
        while (size--) 
        {
            Node* curr = q.front();

            q.pop();
            
            if (curr->left != nullptr)
                q.push(curr->left);
            if (curr->right != nullptr)
                q.push(curr->right);
        }
        
        nodeCount *= 2;
    }
    
    return true;
}

int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(12);
    root->left->left = newNode(2);
    root->left->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(14);

    cout<<solution(root);

    return 0;
}

Output

1