Check whether a binary tree is a full binary tree or not | Iterative Approach | C ++ implementation to check whether a binary tree is a full binary tree or not ; structure of a node of binary tree ; function to get a new node ; allocate space ; put in the data ; function to check whether a binary tree is a full binary tree or not ; if tree is empty ; queue used for level order traversal ; push ' root ' to ' q ' ; traverse all the nodes of the binary tree level by level until queue is empty ; get the pointer to ' node ' at front of queue ; if it is a leaf node then continue ; if either of the child is not null and the other one is null , then binary tree is not a full binary tee ; push left and right childs of ' node ' on to the queue ' q ' ; binary tree is a full binary tee ; Driver program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; Node * getNode ( int data ) { Node * newNode = ( Node * ) malloc ( sizeof ( Node ) ) ; newNode -> data = data ; newNode -> left = newNode -> right = NULL ; return newNode ; } bool isFullBinaryTree ( Node * root ) { if ( ! root ) return true ; queue < Node * > q ; q . push ( root ) ; while ( ! q . empty ( ) ) { Node * node = q . front ( ) ; q . pop ( ) ; if ( node -> left == NULL && node -> right == NULL ) continue ; if ( node -> left == NULL node -> right == NULL ) return false ; q . push ( node -> left ) ; q . push ( node -> right ) ; } return true ; } int main ( ) { Node * root = getNode ( 1 ) ; root -> left = getNode ( 2 ) ; root -> right = getNode ( 3 ) ; root -> left -> left = getNode ( 4 ) ; root -> left -> right = getNode ( 5 ) ; if ( isFullBinaryTree ( root ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }