What is Full Binary Tree?

A full binary tree is a type of binary tree in which every node has either zero or two children.

Full Binary Tree example

Properties of Full Binary Tree:

Let i be the number of internal nodes, n be the total number of nodes, l be the number of leaf nodes and h be the total number of levels

• The number of leaves is (i + 1).
• The total number of nodes is (2*i + 1).
• The number of internal nodes is (n – 1) / 2.
• The number of leaves is (n + 1) / 2.
• The total number of nodes is (2*l – 1).
• The number of internal nodes is (l – 1).
• The number of leaves is at most (2^h – 1).

How to identify a Full Binary Tree:

To determine if a given binary tree is a full binary tree, we can use the following steps:

• Traverse the tree using any traversal algorithm (in order, preorder, postured, level order).
• For each internal node (non-leaf node), check if it has exactly two children. 
  • If it does not have exactly two children, then the tree is not a full binary tree.
  • If all internal nodes have exactly two children, then the tree is a full binary tree.

To see the implementation and details of how to identify, refer to this article.

What else can you read?

• Full Binary Tree
• Check whether a binary tree is full or not
• Print all possible N nodes full binary tree