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

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

Data Structure  

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

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

Cool !!! How to find the diameter of a binary tree

Cool !!! How to find the diameter of a binary tree

Diameter of a Binary Tree  

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of path between two nodes is represented by the number of edges between them.
From the given below Binary tree diameter for both will be 9.

Lets see simple java code to create binary tree with the given array of integers and need to find the diameter of that.

class BST {
 BST left, right;
 int data;

 public BST(int data) {
  this.data = data;
  left = right = null;
 }
}

public class BinaryTreeDiameter {

 public static void main(String[] args) {

  int val[] = new int[] { 18,10,20,22,4,13,3,12,14,2,1,11,15,16,17 };

  BinaryTreeDiameter obj = new BinaryTreeDiameter();

  BST root = obj.createBinaryTree(val);
  
  System.out.println("Diameter : "+obj.findDiameter(root));
 }

 public int findDiameter(BST root) {
  if(root == null) return 0;
  
  int h1 = getHeight(root.left) + getHeight(root.right);
  int lh = findDiameter(root.left);
  int rh = findDiameter(root.right);
  return Math.max(h1, Math.max(lh, rh));
 }
 
 public int getHeight(BST root) {
  
  if(root == null) return 0;
  
  int lh = getHeight(root.left);
  int rh = getHeight(root.right);
  return 1 + Math.max(lh, rh);
 }
 
 public BST createBinaryTree(int[] val) {
  BST root = new BST(val[0]); // Initialize root with 1ft element
  BST tmpRoot = root; // Temporary root node

  for (int i = 1; i < val.length; i++) {

   BST lastNode = getLastNode(tmpRoot, val[i]);
   if (val[i] > lastNode.data) {
    BST tmp = new BST(val[i]);
    lastNode.right = tmp;
   } else {
    BST tmp = new BST(val[i]);
    lastNode.left = tmp;
   }
  }
  return root;
 }

 public BST getLastNode(BST root, int val) {

  if (val > root.data) {
   if (root.right == null) {
    return root;
   } else
    return getLastNode(root.right, val);
  } else {
   if (root.left == null) {
    return root;
   } else
    return getLastNode(root.left, val);
  }
 }
}

OUTPUT:

Diameter : 9

Know How to find all leaf nodes in binary tree

Know How to find all leaf nodes in binary tree

Print all leaf nodes of a Binary Tree from left to right  

Create a Binary Tree with from the given array of values and then find all the leaf nodes from left to right. Leaf nodes are nothing but bottom/last nodes with both left and right subtree's are null.
For the below given Binary tree the list of leaf nodes will be 1, 6, 9

Lets see simple java code to create a binary with the given array of integers and to find the leaf nodes.

public class BinaryTreeLeafNode {

 public static void main(String[] args) {

  int val[] = new int[] { 4, 5, 8, 100, 3, 2, 9, 1, 7, 6 };
  
  BinaryTree obj = new BinaryTree();

  BST root = obj.createBinaryTree(val);

  obj.getAllLeafNodes(root);
 }

 public BST createBinaryTree(int[] val) {
  BST root = new BST(val[0]); // Initialize root with 1ft element
  BST tmpRoot = root; // Temporary root node

  for (int i = 1; i < val.length; i++) {

   BST lastNode = getLastNode(tmpRoot, val[i]);
   if (val[i] > lastNode.data) {
    BST tmp = new BST(val[i]);
    lastNode.right = tmp;
   } else {
    BST tmp = new BST(val[i]);
    lastNode.left = tmp;
   }
  }
  return root;
 }

 public void getAllLeafNodes(BST root) {
  if (root.left != null) {
   getAllLeafNodes(root.left);
  }
  if (root.right != null) {
   getAllLeafNodes(root.right);
  }
  /*
   * If both left and right are null then its leaf node
   */
  if(root.left == null && root.right == null) {
   System.out.print(root.data + ", ");
  }
 }

 public BST getLastNode(BST root, int val) {

  if (val > root.data) {
   if (root.right == null) {
    return root;
   } else
    return getLastNode(root.right, val);
  } else {
   if (root.left == null) {
    return root;
   } else
    return getLastNode(root.left, val);
  }
 }
}

OUTPUT:

1, 6, 9,