Check whether a binary tree is a full binary tree or not - GeeksforGeeks
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.
http://www.ideserve.co.in/learn/check-whether-binary-tree-is-full-binary-tree-or-not
Read full article from Check whether a binary tree is a full binary tree or not - GeeksforGeeks
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.
To check whether a binary tree is a full binary tree we need to test the following cases:-
1) If a binary tree node is NULL then it is a full binary tree.
2) If a binary tree node does have empty left and right sub-trees, then it is a full binary tree by definition
3) 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.
4) In all other combinations of right and left sub-trees, the binary tree is not a full binary tree.
2) If a binary tree node does have empty left and right sub-trees, then it is a full binary tree by definition
3) 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.
4) In all other combinations of right and left sub-trees, the binary tree is not a full binary tree.
/* 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;} public boolean checkIfFull() { if (root == null) return true; LinkedList<TreeNode> queue = new LinkedList(); boolean hasLeftChild, hasRightChild; queue.add(root); while (!queue.isEmpty()) { TreeNode currentNode = queue.remove(); hasLeftChild = (currentNode.left != null); hasRightChild = (currentNode.right != null); if ((hasLeftChild && !hasRightChild) || (!hasLeftChild && hasRightChild)) { return false; } if (hasLeftChild && hasRightChild) { queue.add(currentNode.left); queue.add(currentNode.right); } } return true; }