This post is completed by 3 users

  • 1
Add to List
Beginner

425. 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:

  1. Do postorder traversal.
  2. Check if the node is a leaf node (means node does not have either left or right child node), return true.
  3. Check if the node has only one child (either left or right child node), return false.
  4. Make a recursive call to the left and right child and do AND before returning the result.
  5. See the image below for more understanding.

Output:

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

Reference: here