Check whether a binary tree is a full binary tree or not | Iterative Approach | Java 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
import java . util . * ; class GfG { static class Node { int data ; Node left , right ; } static Node getNode ( int data ) { Node newNode = new Node ( ) ; newNode . data = data ; newNode . left = null ; newNode . right = null ; return newNode ; } static boolean isFullBinaryTree ( Node root ) { if ( root == null ) return true ; Queue < Node > q = new LinkedList < Node > ( ) ; q . add ( root ) ; while ( ! q . isEmpty ( ) ) { Node node = q . peek ( ) ; q . remove ( ) ; if ( node . left == null && node . right == null ) continue ; if ( node . left == null node . right == null ) return false ; q . add ( node . left ) ; q . add ( node . right ) ; } return true ; } public static void main ( String [ ] args ) { 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 ) ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } }