Showing posts with label Counting nodes in a tree? Yes how to get Binary Tree size. Show all posts
Showing posts with label Counting nodes in a tree? Yes how to get Binary Tree size. Show all posts

Counting nodes in a tree? Yes how to get Binary Tree size

Counting nodes in a tree? Yes how to get Binary Tree size nothing but counting all the nodes in a Binary Tree. For example the size of the below binary tree is 11
Counting nodes in a tree? Yes how to get Binary Tree size

Lets see simple Java code to create Binary Tree and to find the size of the tree as well.


class Node {
 Node left, right;
 int data;

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

public class BinaryTreeSize {

 public static void main(String[] args)  {

  int a[] = { 11, 6, 19, 4, 8, 17, 43, 5, 10, 31, 49 };
  Node root = null;
  BinaryTreeSize tree = new BinaryTreeSize();

  for (int i = 0; i < a.length; i++) {
   root = tree.insertNode(root, a[i]);
  }

  int count = tree.binaryTreeSize(root);
  System.out.println("Binary Tree size : " + count);
 }

 public int binaryTreeSize(Node root) {
  return nodeCount(root, 0);
 }

 /*
  * Getting binary tree size using recursive algorithm
  */
 public int nodeCount(Node root, int val) {
  if (root != null) {
   val++;
   val = nodeCount(root.left, val);
   val = nodeCount(root.right, val);
  }
  return val;
 }

 public Node insertNode(Node root, int data) {
  Node currentNode = new Node(data);
  if (root == null) {
   root = currentNode;
  } else {
   insertData(currentNode, root);
  }
  return root;
 }

 public Node insertData(Node newNode, Node root) {

  if (root.data < newNode.data) {
   if (root.right == null) {
    root.right = newNode;
   } else {
    return insertData(newNode, root.right);
   }
  } else if (root.data > newNode.data) {
   if (root.left == null) {
    root.left = newNode;
   } else {
    return insertData(newNode, root.left);
   }
  }
  return root;
 }
}


OUTPUT:


Binary Tree size : 11