Objective: Given a binary tree, write an algorithm to check if the tree is Full or not.
Full binary tree: A binary tree T is full if each node is either a leaf or possesses exactly two child nodes. See the example below
- Do postorder traversal.
- Check if the node is a leaf node (means node does not have either left or right child node), return true.
- Check if the node has only one child (either left or right child node), return false.
- Make a recursive call to the left and right child and do AND before returning the result.
- See the image below for more understanding.
Given binary is FULL tree: true Given binary is FULL tree: false