Check if given binary tree is full.

Given a binary tree we have to check whether the it is a full binary tree or not.

A full B-tree is defined as a binary tree in which all nodes have either zero or two child nodes.

Alternatively we can say there is no node in a full B-tree, which has only one child node.

Example

Input:
Input : 
           1
         /   \
        2     3
       / \  
      4   5
Output : Yes

Input :
           1
         /   \
        2     3
       /  
      4   
Output :No

We are going to see the both iterative and recursive solution for it.

Recursively check if B-tree is a full or not.

Conceptually this how the solution works.

• Create a function which recursively calls itself to check if each node has 0 or 2 child or not.
• If the the given node is empty then its a full binary tree.
• If given node has no child then also it is full.
• If it has left and right both child then it is full.
• Other wise it is not a full binary tree.

const isFullTreeRecursive = (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 subtrees are not null 
  // the are full 
  if((root.left !== null) && (root.right !== null)) {
    return (isFullTreeRecursive(root.left) && isFullTreeRecursive(root.right));
  }

  // if none work 
  return false; 
} 

Input:
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

let tree = new Node(10); 
tree.left = new Node(20); 
tree.right = new Node(30); 
tree.left.right = new Node(40); 
tree.left.left = new Node(50); 
tree.right.left = new Node(60); 
tree.left.left.left = new Node(80); 
tree.right.right = new Node(70); 
tree.left.left.right = new Node(90); 
tree.left.right.left = new Node(80); 
tree.left.right.right = new Node(90); 
tree.right.left.left = new Node(80); 
tree.right.left.right = new Node(90); 
tree.right.right.left = new Node(80); 
tree.right.right.right = new Node(90);

console.log(isFullTreeRecursive(tree));

Output:
true

Time complexity: O(n).
Space complexity: O(n) considering the call stack, O(1) otherwise.

---

Iterative solution using queue to check full B-tree.

We can implement the above recursive solution iteratively using queue.

• Add the root to the queue.
• Keep iterating while queue is not empty.
• In each iteration get the first value from the queue and check if it has 0 or 2 child then continue and add those child’s back to the queue.
• Other wise return false.

const isFullTreeIterative = (root) => {
  if(root === null){
    return true;
  }
  
  const q = [];
  
  //Add the root to the queue initially
  q.unshift(root);
  
  // traverse all the nodes of the binary tree  
  // level by level until queue is empty  
  while(q.length){
    const node = q.pop();
    
    //If it is a leaf then continue
    if(node.left === null && node.right === null){
      continue;
    }
    
    // if either of the child is not null and the  
    // other one is null, then binary tree is not  
    // a full binary tee  
    if (node.left === null || node.right === null) {
      return false;  
    }

    // push left and right childs of 'node'  
    // on to the queue 'q'  
    q.unshift(node.left);  
    q.unshift(node.right); 
  }
  
  // binary tree is a full binary tee  
  return true;  
}

Input:
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

let tree = new Node(10); 
tree.left = new Node(20); 
tree.right = new Node(30); 
tree.left.right = new Node(40); 
tree.left.left = new Node(50); 
tree.right.left = new Node(60); 
tree.left.left.left = new Node(80); 
tree.right.right = new Node(70); 
tree.left.left.right = new Node(90); 
tree.left.right.left = new Node(80); 
tree.left.right.right = new Node(90); 
tree.right.left.left = new Node(80); 
tree.right.left.right = new Node(90); 
tree.right.right.left = new Node(80); 
tree.right.right.right = new Node(90);

console.log(isFullTreeIterative(tree));

Output:
true

Time complexity: O(n).
Space complexity: O(n).