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

How to do Iterative Postorder Traversal in BST

How to do Iterative Postorder Traversal in BST

Postorder  

Earlier we have seen lot of tutorials related to Binary Search Tree like

How to find the diameter of a binary tree
Converting a Binary Tree into its Mirror Tree
Inorder Predecessor and Successor of Binary Search Tree
How to find all leaf nodes in Binary Search Tree

In this tutorial we will see how to do postorder traversal using iterative method instead of recrusive algorithm. We are going to use single stack to store nodes and applying our logic over it to get postorder traversal.

Simple Java code to create Binary Search Tree and doing postorder traversal using iterative method.

import java.util.Stack;

class Node {
 Node left, right;
 int data;

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

public class PostOrderTraversal {

 public static void main(String[] args)  {

  int a[] = { 4, 5, 8, 100, 3, 2, 9, 1, 7, 6 };
  Node root = null;
  PostOrderTraversal tree = new PostOrderTraversal();

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

  System.out.println("\n\nBy Stack : ");
  tree.postOrderTraversal(root);

 }

 /*
  * Postorder traversal using iteration and single stack
  */
 public void postOrderTraversal(Node root)  {

  //Stack to store each node
  Stack<Node> stack = new Stack<Node>();

  //Strong all left node from root into stack
  while (root != null) {
   stack.push(root);
   root = root.left;
  }
  Node node = null;

  while (stack.size() > 0) {

   // Boolean flag to check left and right nodes are visited or not
   boolean leftVisited = false, rightVisited = false;

   // Checking whether current node is equal to roots left node (1)
   if (node != null && stack.peek().left == node) {
    leftVisited = true;

   // Checking whether current node is equal to roots right node (2)
   } else if (node != null && stack.peek().right == node) {
    leftVisited = rightVisited = true;

   }
   node = stack.peek();

   // if above check (1) fails then push current nodes left node into stack
   if (node.left != null && !leftVisited) {
    stack.push(node.left);
   // if above check (2) fails then push current nodes right node into stack
   } else if (node.right != null && !rightVisited) {
    stack.push(node.right);

   } else {
    node = stack.pop();
    System.out.print(node.data + ", ");
   }
  }
 }

 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:

By Stack : 
1, 2, 3, 6, 7, 9, 100, 8, 5, 4, 

How to write a simple and easy Binary search algorithm

How to write a simple and easy Binary search algorithm

Interview Questions  

Given a sorted array array[] of n elements and need to find the element 'val' present in the array or not by using Binary search technique.

NOTE: Binary search works only on sorted array.

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Example: 
Array[] = { 3, 7, 9, 10, 12, 15, 18, 23, 27, 29, 30, 32, 36, 39, 41, 43, 54 }
value = 10

OUTPUT: 3 (10 found in 3rd index)


Array[] = { 3, 7, 9, 10, 12, 15, 18, 23, 27, 29, 30, 32, 36, 39, 41, 43, 54 }
value = 99

OUTPUT: -1 (99 not present in the array)

Lets see simple java code for Binary Search.

public class BinarySearch {

 public static void main(String[] args) {

  int array[] = new int[] { 3, 7, 9, 10, 12, 15, 18, 23, 27, 29, 30, 32, 36, 39, 41, 43, 54 };
  int find = 10;

  int output = new BinarySearch().binarySearch(array, find);

  System.out.println(output);
 }

 public int binarySearch(int[] array, int val) {

  int p = 0, r = array.length - 1;

  while (p <= r) {
   int q = (p + r) / 2;
   if (array[q] == val)
    return q;
   if (array[q] > val)
    r = q - 1;
   else
    p = q + 1;
  }
  // number not present in the array
  return -1;
 }
}

OUTPUT:

3

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, 

Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java

Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java

Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java  

The Longest Common Subsequence (LCS) problem is given with two strings like "ABAZDC" and "BACBAD". LCS is to find their longest common subsequence that appear left-to-right but not necessarily in a contiguous block in both the strings. Here we will see how to achieve Longest Common Subsequence (LCS) algorithm using Dynamic Programming using Java.

Example:
Str1 = "ABAZDC"
Str2 = "BACBAD"

Here the Longest Common Subsequence (LCS) size will be 4 and the Longest Common Subsequence (LCS) will "ABAD".

How to find Longest Common Subsequence (LCS)?

First we need to construct matrix of size str1 and str2 like matrix[str1.length][str2.matrix] as shown below

Whenever any character matches with both the array then we need to increment the value by 1 and carry on with same comparison for all rows and columns.
Same comparison will be done using recursion and by storing the value to achieve dynamic programming.  

public class LCS {

 public static void main(String[] args) {

  String str1 = "ABAZDC";
  String str2 = "BACBAD";

  LCS obj = new LCS();
  String out = obj.getLCS(str1, str2);

  System.out.println("LCS Length : " + out.length());
  System.out.println("LCS String : " + out);
 }

 public String getLCS(String str1, String str2) {

  /* Array will be updated with the character change order */
  int arr[][] = new int[str1.length()][str2.length()];
  
  /* Calling actual LCS recursive method */
  getLCS(str1, str1.length() - 1, str2, str2.length() - 1, arr);

  return constructLCSString(arr, str1, str2);
 }
 
 /*
  * Constructing the LCS string the generated array arr[]
  */
 public String constructLCSString(int[][] arr, String str1, String str2) {
  
  String lcsString = "";
  
  /* Iterating through arr[] to get the actual LCS string 
   * iterating from bottom to up.
   */
  for (int i = arr.length - 1, j = arr[0].length - 1; (i >= 0 && j >= 0);) {

   if (i == 0) {
    lcsString = str1.charAt(i) + lcsString;
    break;
   } else if (j == 0) {
    lcsString = str2.charAt(j) + lcsString;
    break;
   }

   if (arr[i][j] != arr[i - 1][j] && arr[i][j] != arr[i][j - 1]) {
    lcsString = str1.charAt(i) + lcsString;
    i--;j--;
   } else if (arr[i][j] == arr[i - 1][j]) {
    i--;
   } else if (arr[i][j] == arr[i][j - 1]) {
    j--;
   }
  }
  return lcsString;
 }
 
 
 public int getLCS(String str1, int n, String str2, int m, int arr[][]) {
  if (n == -1 || m == -1)
   return 0;
  
  /*
   * Checking in array for same n, m index and if present returning 
   * the value from array and its Dynamic programming
   */
  if (arr[n][m] != 0)
   return arr[n][m];

  int output = 0;
  if (str1.charAt(n) == str2.charAt(m)) {
   output = 1 + getLCS(str1, n - 1, str2, m - 1, arr);
  } else {
   int tmp1 = getLCS(str1, n - 1, str2, m, arr);
   int tmp2 = getLCS(str1, n, str2, m - 1, arr);
   output = tmp1 > tmp2 ? tmp1 : tmp2;
  }
  /* Memorize the output on array to use for similar recursive call */
  arr[n][m] = output;
  return output;
 }
}

OUTPUT:

LCS Length : 4
LCS String : ABAD