Find number of full and half nodes in binary tree

byNikhil Ranjan •
1
Problem Statement :- Find Number of full-nodes in given binary tree.
Full-node of binary tree  - has both left and right child non-null.
Half node of binary tree is 
Left Binary tree(Tree 1) and Right binary tree(Tree 2)
No of full and half nodes of binary tree(left side) :-    5 and 2
No of full and half nodes of binary tree(right side) :-  2 and 3

Number of full and half nodes of binary tree - Iterative approach 
Algorithm : Idea here is to do level order traversal and check for whether left and right child is not null for a given node. If true, increment count for fullNodeCount and similarly, if one of the left or right child is null, increment count of halfNodeCount.
1. Loop until queue is not empty.
2. Do check for null condition of left and right child, if true increment count for fullNodeCount(both left and right is not null) and halfNodeCount (One of left and right is null).
3. Once all nodes has been traversed, fullNodeCount and halfNodeCount has number of full nodes and half nodes of binary tree.
Time and space complexity :- TC = O(n) and SC = O(n), n is number of nodes in given binary tree.
Sample code for finding number of full nodes and half nodes in binary tree
/* Iterative method to find no. full nodes in a binary tree. */
public int[] findNumberOfFullNodesIterative(Node root) {
 int[] fullNhalfNodesCount = { 0, 0 };
 Queue<Node> queue = new ArrayDeque<>();
 queue.add(root);
 if (root != null) {
  while (!queue.isEmpty()) {
   root = queue.remove();
   /* Full node has both left and right child */
   if (root.leftChild != null && root.rightChild != null) {
    fullNhalfNodesCount[0] += 1;
   }
   /* Half node has one of the left and right child is null */
   if ((root.leftChild == null || root.rightChild == null)
     && !(root.leftChild == null && 
     root.rightChild == null)) {
    fullNhalfNodesCount[1] += 1;
   }
   Node lc = root.leftChild;
   Node rc = root.rightChild;
   if (lc != null) {
    queue.add(lc);
   }
   if (rc != null) {
    queue.add(rc);
   }
  }
 }
 return fullNhalfNodesCount;
}

Number of full and half nodes of binary tree - Recursive approach 
Algorithm :- Do recursive pre-order traversal and  check for full/half nodes and increment counter accordingly.
1. Make recursive call and check for full and half nodes.
2. Increment fullNodes[0] for full node and  fullNodes[1] for half nodes. 
3. Once all nodes is traversed, static fullNodes array has count of full/half nodes.
Note:- fullNodes[] is a static array, a class variable.
Sample program for find diameter of binary tree - time complexity O(n)
/* Recursive method to find no. full nodes in a binary tree. */
public void findNumberOfFullNodesRecursive(Node root) {
 if (root == null) {
  return;
 }
 /* Full node has both left and right child */
 if (root.leftChild != null && root.rightChild != null) {
  /* increment static variable */
  fullNodes[0] += 1;
 }
 /* Half node has one of the left and right child is null */
 if ((root.leftChild == null || root.rightChild == null)
   && !(root.leftChild == null && root.rightChild == null)) {
  fullNodes[1] += 1;
 }
 findNumberOfFullNodesRecursive(root.leftChild);
 findNumberOfFullNodesRecursive(root.rightChild);
}

Complete sample program- number of full and half nodes of binary tree 

package com.devinline.trees;

import java.util.ArrayDeque;
import java.util.Queue;

public class FullNodesBinaryTree {
 static int[] fullNodes = { 0, 0 };

 /* Iterative method to find no. full nodes in a binary tree. */
 public int[] findNumberOfFullNodesIterative(Node root) {
  int[] fullNhalfNodesCount = { 0, 0 };
  Queue<Node> queue = new ArrayDeque<>();
  queue.add(root);
  if (root != null) {
   while (!queue.isEmpty()) {
    root = queue.remove();
    /* Full node has both left and right child */
    if (root.leftChild != null && root.rightChild != null) {
     fullNhalfNodesCount[0] += 1;
    }
    /* Half node has one of the left and right child is null */
    if ((root.leftChild == null || root.rightChild == null)
      && !(root.leftChild == null && 
      root.rightChild == null)) {
     fullNhalfNodesCount[1] += 1;
    }
    Node lc = root.leftChild;
    Node rc = root.rightChild;
    if (lc != null) {
     queue.add(lc);
    }
    if (rc != null) {
     queue.add(rc);
    }
   }
  }
  return fullNhalfNodesCount;
 }

 /* Recursive method to find no. full nodes in a binary tree. */
 public void findNumberOfFullNodesRecursive(Node root) {
  if (root == null) {
   return;
  }
  /* Full node has both left and right child */
  if (root.leftChild != null && root.rightChild != null) {
   /* increment static variable */
   fullNodes[0] += 1;
  }
  /* Half node has one of the left and right child is null */
  if ((root.leftChild == null || root.rightChild == null)
    && !(root.leftChild == null && root.rightChild == null)) {
   fullNodes[1] += 1;
  }
  findNumberOfFullNodesRecursive(root.leftChild);
  findNumberOfFullNodesRecursive(root.rightChild);
 }

 public static void main(String[] args) {
  FullNodesBinaryTree nbt = new FullNodesBinaryTree();
  Node root = nbt.new BinaryTree().createTree1();

  int[] count = nbt.findNumberOfFullNodesIterative(root);
  System.out.print("Numbers of full nodes and half nodes "
    + "in binary tree-1 (Iterative): ");
  System.out.println(count[0] + " and " + count[1]);

  nbt.findNumberOfFullNodesRecursive(root);
  System.out.print("Numbers of full nodes and half nodes "
    + "in binary tree-1 (Recursive): ");
  System.out.println(fullNodes[0] + " and " + fullNodes[1]);
  /* Reset static variable to 0 */
  fullNodes[0] = 0;
  fullNodes[1] = 0;

  root = nbt.new BinaryTree().createTree2();
  count = nbt.findNumberOfFullNodesIterative(root);
  System.out.print("Numbers of full nodes and half nodes "
    + "in binary tree-2 (Iterative): ");
  System.out.println(count[0] + " and " + count[1]);
  nbt.findNumberOfFullNodesRecursive(root);
  System.out.print("Numbers of full nodes and half nodes "
    + "in binary tree-2 (Recursive): ");
  System.out.println(fullNodes[0] + " and " + fullNodes[1]);

 }

 class Node {
  private int data;
  private Node leftChild;
  private Node rightChild;

  public Node(int data) {
   this.data = data;
   leftChild = null;
   rightChild = null;
  }

  public int getData() {
   return data;
  }

  public void setData(int data) {
   this.data = data;
  }

  public Node getLeftChild() {
   return leftChild;
  }

  public void setLeftChild(Node leftChild) {
   this.leftChild = leftChild;
  }

  public Node getRightChild() {
   return rightChild;
  }

  public void setRightChild(Node rightChild) {
   this.rightChild = rightChild;
  }
 }

 class BinaryTree {
  Node root;

  public BinaryTree() {
   root = null;
  }

  public Node createTree1() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(23));
   root.setRightChild(new Node(18));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(43));
   root.getRightChild().setRightChild(new Node(27));
   root.getRightChild().setLeftChild(new Node(12));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
   root.getLeftChild().getLeftChild().setRightChild(new Node(78));
   root.getRightChild().getLeftChild().setRightChild(new Node(98));
   root.getRightChild().getLeftChild().setLeftChild(new Node(32));
   root.getLeftChild().getLeftChild().getRightChild()
     .setLeftChild(new Node(87));
   root.getRightChild().getLeftChild().getRightChild()
     .setLeftChild(new Node(29));
   return root;
  }

  public Node createTree2() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(18));
   root.setRightChild(new Node(23));
   root.getLeftChild().setLeftChild(new Node(43));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(143));
   root.getLeftChild().setRightChild(new Node(11));
   root.getLeftChild().getRightChild().setRightChild(new Node(12));
   root.getLeftChild().getRightChild().getRightChild()
     .setLeftChild(new Node(121));
   return root;
  }
 }

}
================Sample output=====================
Numbers of full nodes and half nodes in binary tree-1 (Iterative): 5 and 2
Numbers of full nodes and half nodes in binary tree-1 (Recursive): 5 and 2
Numbers of full nodes and half nodes in binary tree-2 (Iterative): 2 and 3
Numbers of full nodes and half nodes in binary tree-2 (Recursive): 2 and 3
==============================================
Similar problem:- 
1. Find number of leaf nodes in binary tree - Increment count only when both left and right child nodes are null
Tags:

1 Comments

Previous Post Next Post