Sunday, 15 April 2018

How to count the number of leaves in a binary tree?


Hello Buddies.


Here's a quick code snippet for finding the number of leaves in a 'Binary Tree', after a node gets deleted!





Have a look-

Input -

5
-1 0 0 1 1
1


Input description -

Line 1: No. of nodes in Binary Tree
Line 2: All the nodes' parents, where -1 means no parent - root, 0 means root as parent.
Line 3: Node at which this value exists, remove it.


Node to remove -



public class TreeProblem {
 private static int count = 0;

 public static void main(String args[]) throws Exception {

  Scanner scanner = new Scanner(System.in);
  int numOfNodes = scanner.nextInt();
  scanner.nextLine();
  String intStr = scanner.nextLine();
  String[] array = intStr.split(" ");
  int[] arr = new int[array.length];
  for (int i = 0; i < numOfNodes; i++) {
   arr[i] = Integer.valueOf(array[i]);
  }
  int nodeToDelete = scanner.nextInt();

  // create a tree
  Node root = null;
  int valueIndex = 0;
  Node current = null;
  for (int i = 0; i < numOfNodes; i++) {
   if (arr[i] == -1) {
    root = new Node(valueIndex++);
    current = root;
   } else {
    if (arr[i] == current.value) {
     if (null == current.left) {
      current.left = new Node(valueIndex++);
     } else if (null == current.right) {
      current.right = new Node(valueIndex++);
      current = current.left;
     }
    }
   }
  }

  // scan the tree for deleting the node
  // it clearly means we have to ignore the leaves at that node, for the remaining
  // keep the count going

  treetraversal(root, nodeToDelete);

  System.out.println("Remaining leaves = " + count);
  scanner.close();
 }

 private static void treetraversal(Node root, int nodeToDelete) {
  if (null == root) {
   return;
  }
  System.out.println("-- " + root.value);
  if (root.value == nodeToDelete) {
   return;
  }
  if (null != root.left) {
   treetraversal(root.left, nodeToDelete);
  }
  if (null != root.right) {
   treetraversal(root.right, nodeToDelete);
  }
  if (null == root.left && null == root.right) {
   count++;
  }
 }

}

class Node {

 int value;
 Node parent, left, right;

 Node(int value) {
  this.value = value;
 }
}

Featured post

JAVA based project, that can be used to hit DB using JDBC, from WSO2 ESB

Hi Buddies, Here is a small project that will enable you to hit MySQL DB using WSO2 ESB - https://github.com/namitsharma99/customM...

Popular Posts