Check if the given binary tree is Full or not.

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

Approach:

  • 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.

Code:

Output:

Given binary is FULL tree: true
Given binary is FULL tree: false

Reference: here

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: