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 nodestruct Node { int data; Node *left, *right;};// Utility function to allocate memory for a new nodeNode* 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 perfectbool 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 codeint 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 sysimport math# A binary tree nodeclass 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 perfectdef 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 Codeif __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 perfectusing 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 nodeclass Node{ constructor(data) { this.data = data; this.left = this.right = null; }}// Function to check if the given tree is perfectfunction 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 codelet 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
