A full binary tree is defined as a binary tree in which all nodes have either zero or two child nodes. Conversely, there is no node in a full binary tree, which has one child node. More information about full binary trees can be found here.
For Example :
To check whether a binary tree is a full binary tree we need to test the following cases:-
- If a binary tree node is NULL then it is a full binary tree.
- If a binary tree node does have empty left and right sub-trees, then it is a full binary tree by definition.
- If a binary tree node has left and right sub-trees, then it is a part of a full binary tree by definition. In this case recursively check if the left and right sub-trees are also binary trees themselves.
- In all other combinations of right and left sub-trees, the binary tree is not a full binary tree.
Following is the implementation for checking if a binary tree is a full binary tree.
C++
// C++ program to check whether a given Binary Tree is full or not#include <bits/stdc++.h>using namespace std; /* Tree node structure */struct Node{ int key; struct Node *left, *right;}; /* Helper function that allocates a new node with the given key and NULL left and right pointer. */struct Node *newNode(char k){ struct Node *node = new Node; node->key = k; node->right = node->left = NULL; return node;} /* This function tests if a binary tree is a full binary tree. */bool isFullTree (struct Node* root){ // If empty tree if (root == NULL) return true; // If leaf node if (root->left == NULL && root->right == NULL) return true; // If both left and right are not NULL, and left & right subtrees // are full if ((root->left) && (root->right)) return (isFullTree(root->left) && isFullTree(root->right)); // We reach here when none of the above if conditions work return false;} // Driver Programint main(){ struct Node* root = NULL; root = newNode(10); root->left = newNode(20); root->right = newNode(30); root->left->right = newNode(40); root->left->left = newNode(50); root->right->left = newNode(60); root->right->right = newNode(70); root->left->left->left = newNode(80); root->left->left->right = newNode(90); root->left->right->left = newNode(80); root->left->right->right = newNode(90); root->right->left->left = newNode(80); root->right->left->right = newNode(90); root->right->right->left = newNode(80); root->right->right->right = newNode(90); if (isFullTree(root)) cout << "The Binary Tree is full\n"; else cout << "The Binary Tree is not full\n"; return(0);}// This code is contributed by shubhamsingh10 |
C
// C program to check whether a given Binary Tree is full or not#include<stdio.h>#include<stdlib.h>#include<stdbool.h>/* Tree node structure */struct Node{ int key; struct Node *left, *right;};/* Helper function that allocates a new node with the given key and NULL left and right pointer. */struct Node *newNode(char k){ struct Node *node = (struct Node*)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node;}/* This function tests if a binary tree is a full binary tree. */bool isFullTree (struct Node* root){ // If empty tree if (root == NULL) return true; // If leaf node if (root->left == NULL && root->right == NULL) return true; // If both left and right are not NULL, and left & right subtrees // are full if ((root->left) && (root->right)) return (isFullTree(root->left) && isFullTree(root->right)); // We reach here when none of the above if conditions work return false;}// Driver Programint main(){ struct Node* root = NULL; root = newNode(10); root->left = newNode(20); root->right = newNode(30); root->left->right = newNode(40); root->left->left = newNode(50); root->right->left = newNode(60); root->right->right = newNode(70); root->left->left->left = newNode(80); root->left->left->right = newNode(90); root->left->right->left = newNode(80); root->left->right->right = newNode(90); root->right->left->left = newNode(80); root->right->left->right = newNode(90); root->right->right->left = newNode(80); root->right->right->right = newNode(90); if (isFullTree(root)) printf("The Binary Tree is full\n"); else printf("The Binary Tree is not full\n"); return(0);} |
Java
// Java program to check if binary tree is full or not/* Tree node structure */class Node { int data; Node left, right; Node(int item) { data = item; left = right = null; }} class BinaryTree { Node root; /* this function checks if a binary tree is full or not */ boolean isFullTree(Node node) { // if empty tree if(node == null) return true; // if leaf node if(node.left == null && node.right == null ) return true; // if both left and right subtrees are not null // they are full if((node.left!=null) && (node.right!=null)) return (isFullTree(node.left) && isFullTree(node.right)); // if none work return false; } // Driver program public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(10); tree.root.left = new Node(20); tree.root.right = new Node(30); tree.root.left.right = new Node(40); tree.root.left.left = new Node(50); tree.root.right.left = new Node(60); tree.root.left.left.left = new Node(80); tree.root.right.right = new Node(70); tree.root.left.left.right = new Node(90); tree.root.left.right.left = new Node(80); tree.root.left.right.right = new Node(90); tree.root.right.left.left = new Node(80); tree.root.right.left.right = new Node(90); tree.root.right.right.left = new Node(80); tree.root.right.right.right = new Node(90); if(tree.isFullTree(tree.root)) System.out.print("The binary tree is full"); else System.out.print("The binary tree is not full"); }} // This code is contributed by Mayank Jaiswal |
Python3
# Python program to check whether given Binary tree is full or not# Tree node structureclass Node: # Constructor of the node class for creating the node def __init__(self , key): self.key = key self.left = None self.right = None# Checks if the binary tree is full or notdef isFullTree(root): # If empty tree if root is None: return True # If leaf node if root.left is None and root.right is None: return True # If both left and right subtress are not None and # left and right subtress are full if root.left is not None and root.right is not None: return (isFullTree(root.left) and isFullTree(root.right)) # We reach here when none of the above if conditions work return False# Driver Programroot = Node(10);root.left = Node(20);root.right = Node(30);root.left.right = Node(40);root.left.left = Node(50);root.right.left = Node(60);root.right.right = Node(70);root.left.left.left = Node(80);root.left.left.right = Node(90);root.left.right.left = Node(80);root.left.right.right = Node(90);root.right.left.left = Node(80);root.right.left.right = Node(90);root.right.right.left = Node(80);root.right.right.right = Node(90);if isFullTree(root): print ("The Binary tree is full")else: print ("Binary tree is not full")# This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to check if binary tree // is full or not using System;/* Tree node structure */public class Node{ public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }}class GFG{public Node root;/* This function checks if a binarytree is full or not */public virtual bool isFullTree(Node node){ // if empty tree if (node == null) { return true; } // if leaf node if (node.left == null && node.right == null) { return true; } // if both left and right subtrees // are not null they are full if ((node.left != null) && (node.right != null)) { return (isFullTree(node.left) && isFullTree(node.right)); } // if none work return false;}// Driver Code public static void Main(string[] args){ GFG tree = new GFG(); tree.root = new Node(10); tree.root.left = new Node(20); tree.root.right = new Node(30); tree.root.left.right = new Node(40); tree.root.left.left = new Node(50); tree.root.right.left = new Node(60); tree.root.left.left.left = new Node(80); tree.root.right.right = new Node(70); tree.root.left.left.right = new Node(90); tree.root.left.right.left = new Node(80); tree.root.left.right.right = new Node(90); tree.root.right.left.left = new Node(80); tree.root.right.left.right = new Node(90); tree.root.right.right.left = new Node(80); tree.root.right.right.right = new Node(90); if (tree.isFullTree(tree.root)) { Console.Write("The binary tree is full"); } else { Console.Write("The binary tree is not full"); }}}// This code is contributed by Shrikant13 |
Javascript
<script>// javascript program to check if binary tree is full or not/* Tree node structure */class Node { constructor(item) { this.data = item; this.left = this.right = null; }} var root; /* this function checks if a binary tree is full or not */ function isFullTree( node) { // if empty tree if (node == null) return true; // if leaf node if (node.left == null && node.right == null) return true; // if both left and right subtrees are not null // they are full if ((node.left != null) && (node.right != null)) return (isFullTree(node.left) && isFullTree(node.right)); // if none work return false; } // Driver program root = new Node(10); root.left = new Node(20); root.right = new Node(30); root.left.right = new Node(40); root.left.left = new Node(50); root.right.left = new Node(60); root.left.left.left = new Node(80); root.right.right = new Node(70); root.left.left.right = new Node(90); root.left.right.left = new Node(80); root.left.right.right = new Node(90); root.right.left.left = new Node(80); root.right.left.right = new Node(90); root.right.right.left = new Node(80); root.right.right.right = new Node(90); if(isFullTree(root)) document.write("The binary tree is full"); else document.write("The binary tree is not full"); // This code contributed by gauravrajput1 </script> |
Output
The Binary Tree is full
Time complexity: O(n) where n is number of nodes in given binary tree.
Auxiliary Space: O(n) for call stack since using recursion
Iterative Approach:
To check whether a binary tree is a full binary tree we need to test the following cases:-
- Create a queue to store nodes
- Store the root of the tree in the queue
- Traverse until the queue is not empty
- If the current node is not a leaf insert root->left and root->right in the queue.
- If the current node is NULL return false.
- If the queue is empty return true.
Following is the implementation for checking if a binary tree is a full binary tree.
C++
// c++ program to check whether a given BT is full or not#include <bits/stdc++.h>using namespace std;// Tree node structurestruct Node { int val; Node *left, *right;};// fun that creates and returns a new nodeNode* newNode(int data){ Node* node = new Node(); node->val = data; node->left = node->right = NULL; return node;}// helper fun to check leafnodebool isleafnode(Node* root){ return !root->left && !root->right;}// fun checks whether the given BT is a full BT or notbool isFullTree(Node* root){ // if tree is empty if (!root) return true; queue<Node*> q; q.push(root); while (!q.empty()) { root = q.front(); q.pop(); // null indicates - not a full BT if (root == NULL) return false; // if its not a leafnode then the current node // should contain both left and right pointers. if (!isleafnode(root)) { q.push(root->left); q.push(root->right); } } return true;}int main(){ Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); if (isFullTree(root)) cout << "The Binary Tree is full\n"; else cout << "The Binary Tree is not full\n"; return 0;}// This code is contributed by Modem Upendra. |
Java
// Java program to check whether a given BT is full or notimport java.util.ArrayDeque;import java.util.Queue;public class GFG { /* Tree node structure */ static class Node { int data; Node left, right; Node(int item) { data = item; left = right = null; } } // helper fun to check leafnode static boolean isleafnode(Node root) { return root.left == null && root.right == null; } // fun checks whether the given BT is a full BT or not static boolean isFullTree(Node root) { // if tree is empty if (root == null) return true; Queue<Node> q = new ArrayDeque<>(); q.add(root); while (!q.isEmpty()) { root = q.peek(); q.remove(); // null indicates - not a full BT if (root == null) return false; // if its not a leafnode then the current node // should contain both left and right pointers. if (!isleafnode(root)) { q.add(root.left); q.add(root.right); } } return true; } // Driver Code public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); if (isFullTree(root)) System.out.println("The Binary Tree is full"); else System.out.println( "The Binary Tree is not full"); }}// This code is contributed by karandeep1234 |
Python3
# Python program to check whether a given BT is full or not# Tree Structureclass Node: def __init__(self, key): self.data = key self.left = None self.right = None# function that creates and returns a new nodedef newNode(data): node = Node(data) return node# helper function to check leafnodedef isleafnode(root): return root.left is not None and root.right is not None# function checks whether the given BT is a full BT or notdef isFullTree(root): # if tree is empty if root is None: return True q = [] q.append(root) while(len(q) > 0): root = q.pop(0) # null indicates - not a full BT if root is None: return False # if its not a leafnode then the current node # should contain both left and right pointers if isleafnode(root) is False: q.append(root.left) q.append(root.right) return True# Driver program to test above functionroot = newNode(1)root.left = newNode(2)root.right = newNode(3)root.left.left = newNode(4)root.left.right = newNode(5)if isFullTree(root) is True: print("The Binary Tree is full")else: print("The Binary Tree is not full")# This code is contributed by Yash Agarwal(yashagarwal2852002) |
C#
// C# program to check whether a given BT is full or notusing System;using System.Collections.Generic;public class GFG { /* Tree node structure */ public class Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; } } // helper fun to check leafnode static bool isleafnode(Node root) { return root.left == null && root.right == null; } // fun checks whether the given BT is a full BT or not static bool isFullTree(Node root) { // if tree is empty if (root == null) return true; Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count != 0) { root = q.Dequeue(); // null indicates - not a full BT if (root == null) return false; // if its not a leafnode then the current node // should contain both left and right pointers. if (!isleafnode(root)) { q.Enqueue(root.left); q.Enqueue(root.right); } } return true; } // Driver Code public static void Main(string[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); if (isFullTree(root)) Console.WriteLine("The Binary Tree is full"); else Console.WriteLine( "The Binary Tree is not full"); }}// This code is contributed by karandeep1234. |
Javascript
// JAVASCRIPT program to check whether a given BT is full or notclass Queue { constructor() { this.items = []; } // add element to the queue enqueue(element) { return this.items.push(element); } // remove element from the queue dequeue() { if(this.items.length > 0) { return this.items.shift(); } } // view the last element peek() { return this.items[0]; } // check if the queue is empty isEmpty(){ return this.items.length == 0; } // the size of the queue size(){ return this.items.length; } // empty the queue clear(){ this.items = []; }}// Tree node structureclass Node { constructor(item) { this.data = item; this.left = this.right = null; }}// helper fun to check leafnodefunction isleafnode(root){ if(root.left==null && root.right==null) return true; return false; }// fun checks whether the given BT is a full BT or notfunction isFullTree( root){ // if tree is empty if (root==null) return true; let q = new Queue(); q.enqueue(root) while (q.size()!=0) { root = q.peek(); q.dequeue(); // null indicates - not a full BT if (root == null) return false; // if its not a leafnode then the current node // should contain both left and right pointers. if (isleafnode(root)==false) { q.enqueue(root.left); q.enqueue(root.right); } } return true;} let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); if (isFullTree(root)== true) console.log("The Binary Tree is full"); else console.log("The Binary Tree is not full"); // This code is contributed by garg28harsh. |
Output
The Binary Tree is full
Time Complexity: O(N), Where N is the total nodes in a given binary tree.
Auxiliary Space: O(N), in most cases the last level contains nodes as half of the total nodes. O(N/2) ~ 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!
