Iterative approach to check if a Binary Tree is Perfect

0 0 7 minutes read

Given a Binary Tree, the task is to check whether the given Binary Tree is a perfect Binary Tree or not.
A Binary tree is a Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.
Examples:

Input : 
          1
         /  \
        2    3
       / \   / \
      4   5 6   7
Output : Yes

Input :
           20
         /   \
        8     22
       / \    / \
      5   3  4   25
     / \  / \     \
    1  10 2  14    6
Output : No 
One leaf node with value 4 is not present at the 
last level and node with value 25 has 
only one child.

We have already discussed the recursive approach. In this post, the iterative approach is discussed.
Approach: The idea is to use a queue and a variable flag, initialized to zero, to check if a leaf node has been discovered. We will check:

If the current node has two children then we will check for the value of flag. If the value of flag is zero then push the left and right child in the queue, but if the value of flag is one then return false because then that means a leaf node has already been found and in a perfect binary tree all the leaf nodes must be present at the last level, no leaf node should be present at any other level.
If the current node has no child, that means it is a leaf node, then mark flag as one.
If the current node has just one child then return false, as in a perfect binary tree all the nodes have two children except for the leaf nodes, which must be present at the last level of the tree.

Below is the implementation of the above approach:

C++

// C++ program to check if the
// given binary tree is perfect
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree node
struct Node {
    int data;
    Node *left, *right;
};
 
// Utility function to allocate memory for a new node
Node* newNode(int data)
{
    Node* node = new (Node);
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
 
// Function to check if the given tree is perfect
bool CheckPerfectTree(Node* root)
{
    queue<Node*> q;
 
    // Push the root node
    q.push(root);
 
    // Flag to check if leaf nodes have been found
    int flag = 0;
 
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
 
        // If current node has both left and right child
        if (temp->left && temp->right) {
            // If a leaf node has already been found
            // then return false
            if (flag == 1)
                return false;
 
            // If a leaf node has not been discovered yet
            // push the left and right child in the queue
            else {
                q.push(temp->left);
                q.push(temp->right);
            }
        }
 
        // If a leaf node is found mark flag as one
        else if (!temp->left && !temp->right) {
            flag = 1;
        }
 
        // If the current node has only one child
        // then return false
        else if (!temp->left || !temp->right)
            return false;
    }
 
    // If the given tree is perfect return true
    return true;
}
 
// Driver code
int main()
{
    Node* root = newNode(7);
    root->left = newNode(5);
    root->right = newNode(6);
    root->left->left = newNode(8);
    root->left->right = newNode(1);
    root->right->left = newNode(3);
    root->right->right = newNode(9);
    root->right->right->right = newNode(13);
    root->right->right->left = newNode(10);
 
    if (CheckPerfectTree(root))
        printf("Yes");
    else
        printf("No");
 
    return 0;
}

Java

// Java program to check if the 
// given binary tree is perfect 
import java.util.*;
 
class GFG
{
     
// A binary tree node 
static class Node 
{ 
    int data; 
    Node left, right; 
}; 
 
// Utility function to allocate memory for a new node 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
 
// Function to check if the given tree is perfect 
static boolean CheckPerfectTree(Node root) 
{ 
    Queue<Node> q = new LinkedList<Node>(); 
 
    // add the root node 
    q.add(root); 
 
    // Flag to check if leaf nodes have been found 
    int flag = 0; 
 
    while (q.size() > 0)
    { 
        Node temp = q.peek(); 
        q.remove(); 
 
        // If current node has both left and right child 
        if (temp.left != null && temp.right != null) 
        { 
            // If a leaf node has already been found 
            // then return false 
            if (flag == 1) 
                return false; 
 
            // If a leaf node has not been discovered yet 
            // add the left and right child in the queue 
            else
            { 
                q.add(temp.left); 
                q.add(temp.right); 
            } 
        } 
 
        // If a leaf node is found mark flag as one 
        else if (temp.left == null && temp.right == null) 
        { 
            flag = 1; 
        } 
 
        // If the current node has only one child 
        // then return false 
        else if (temp.left == null || temp.right == null) 
            return false; 
    } 
 
    // If the given tree is perfect return true 
    return true; 
} 
 
// Driver code 
public static void main(String args[])
{ 
    Node root = newNode(7); 
    root.left = newNode(5); 
    root.right = newNode(6); 
    root.left.left = newNode(8); 
    root.left.right = newNode(1); 
    root.right.left = newNode(3); 
    root.right.right = newNode(9); 
    root.right.right.right = newNode(13); 
    root.right.right.left = newNode(10); 
 
    if (CheckPerfectTree(root)) 
        System.out.printf("Yes"); 
    else
        System.out.printf("No"); 
} 
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to check if the 
# given binary tree is perfect 
import sys
import math
 
# A binary tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Utility function to allocate 
# memory for a new node 
def newNode(data):
    return Node(data)
 
# Function to check if the 
# given tree is perfect
def CheckPerfectTree(root):
    q = []
 
    # Push the root node
    q.append(root)
 
    # Flag to check if leaf nodes 
    # have been found 
    flag = 0
     
    while(q):
        temp = q[0]
        q.pop(0)
 
        # If current node has both 
        # left and right child
        if (temp.left and temp.right):
             
            # If a leaf node has already been found 
            # then return false 
            if (flag == 1):
                return False
 
            # If a leaf node has not been discovered yet 
            # push the left and right child in the queue 
            else:
                q.append(temp.left)
                q.append(temp.right)
 
        # If a leaf node is found 
        # mark flag as one     
        elif(not temp.left and
             not temp.right):
            flag = 1
 
        # If the current node has only one child 
        # then return false 
        elif(not temp.left or
             not temp.right):
            return False
             
    # If the given tree is perfect
    # return true
    return True
 
# Driver Code
if __name__=='__main__':
    root = newNode(7)
    root.left = newNode(5)
    root.left.left = newNode(8)
    root.left.right = newNode(1)
    root.right = newNode(6)
    root.right.left = newNode(3)
    root.right.right = newNode(9)
    root.right.right.left = newNode(10)
    root.right.right.right = newNode(13)
 
    if CheckPerfectTree(root):
        print("Yes")
    else:
        print("No")
 
# This code is contributed
# by Vikash Kumar 37

C#

// C# program to check if the 
// given binary tree is perfect
using System;
using System.Collections.Generic; 
     
class GFG
{
     
// A binary tree node 
public class Node 
{ 
    public int data; 
    public Node left, right; 
}; 
 
// Utility function to allocate
// memory for a new node 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
 
// Function to check if the given tree is perfect 
static Boolean CheckPerfectTree(Node root) 
{ 
    Queue<Node > q = new Queue<Node>(); 
 
    // add the root node 
    q.Enqueue(root); 
 
    // Flag to check if leaf nodes
    // have been found 
    int flag = 0; 
 
    while (q.Count > 0)
    { 
        Node temp = q.Peek(); 
        q.Dequeue(); 
 
        // If current node has both 
        // left and right child 
        if (temp.left != null && 
            temp.right != null) 
        { 
            // If a leaf node has already been found 
            // then return false 
            if (flag == 1) 
                return false; 
 
            // If a leaf node has not been discovered yet 
            // add the left and right child in the queue 
            else
            { 
                q.Enqueue(temp.left); 
                q.Enqueue(temp.right); 
            } 
        } 
 
        // If a leaf node is found mark flag as one 
        else if (temp.left == null &&
                 temp.right == null) 
        { 
            flag = 1; 
        } 
 
        // If the current node has only one child 
        // then return false 
        else if (temp.left == null ||
                 temp.right == null) 
            return false; 
    } 
 
    // If the given tree is perfect return true 
    return true; 
} 
 
// Driver code 
public static void Main(String []args)
{ 
    Node root = newNode(7); 
    root.left = newNode(5); 
    root.right = newNode(6); 
    root.left.left = newNode(8); 
    root.left.right = newNode(1); 
    root.right.left = newNode(3); 
    root.right.right = newNode(9); 
    root.right.right.right = newNode(13); 
    root.right.right.left = newNode(10); 
 
    if (CheckPerfectTree(root)) 
        Console.WriteLine("Yes"); 
    else
        Console.WriteLine("No"); 
} 
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// Javascript program to check if the
// given binary tree is perfect
 
// A binary tree node
class Node
{
    constructor(data)
    {
        this.data = data;
        this.left = this.right = null;
    }
}
 
// Function to check if the given tree is perfect
function CheckPerfectTree(root)
{
    let q = [];
  
    // add the root node
    q.push(root);
  
    // Flag to check if leaf nodes have been found
    let flag = 0;
  
    while (q.length > 0)
    {
        let temp = q[0];
        q.shift();
  
        // If current node has both left and right child
        if (temp.left != null && temp.right != null)
        {
            // If a leaf node has already been found
            // then return false
            if (flag == 1)
                return false;
  
            // If a leaf node has not been discovered yet
            // add the left and right child in the queue
            else
            {
                q.push(temp.left);
                q.push(temp.right);
            }
        }
  
        // If a leaf node is found mark flag as one
        else if (temp.left == null && temp.right == null)
        {
            flag = 1;
        }
  
        // If the current node has only one child
        // then return false
        else if (temp.left == null || temp.right == null)
            return false;
    }
  
    // If the given tree is perfect return true
    return true;
}
 
// Driver code
let root = new Node(7);
root.left = new Node(5);
root.right = new Node(6);
root.left.left = new Node(8);
root.left.right = new Node(1);
root.right.left = new Node(3);
root.right.right = new Node(9);
root.right.right.right = new Node(13);
root.right.right.left = new Node(10);
 
if (CheckPerfectTree(root))
    document.write("Yes");
else
    document.write("No");
 
// This code is contributed by avanitrachhadiya2155
</script>

Output:

No

Time Complexity: O(N), where N is the total number of nodes in the binary tree.
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!