Showing posts with label Data Structure. Show all posts
Showing posts with label Data Structure. 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

How to do Iterative Postorder Traversal in BST

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.
How to do Iterative Postorder Traversal in BST
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 detect loop in a linked list or not

We have seen lot of posts related to LinkedList like,

How to create Linked List
Finding N'th node from the end of a Linked List
Find the middle node of a given linked list
Merge 2 Sorted Linked Lists
Stack implementation using Linked List
Reverse LinkedList

now lets see how to detect or find whether the linked having loop or not. For example if we traverse the linked list then it will be indefinite and falls into a cyclic loop of entire linked list or within the linked list.
Lets create simple linked list by having loop and by another method lets try to find the loop present or not. We can solve/ find the loop in linked list using multiple ways like

How to detect loop in a linked list or not
  • Storing the NODE in HashSet and checking for each put whether we have same NODE already in HashSet or not. If its present then loop present.
  • Next keep 2 pointers to traverse the nodes like 1st pointer will traverse 1 NODE at a time and 2nd pointer will traverse 2 NODE's at time. At some point 1st and 2nd pointer's will be same and then loop present or else loop not present.
Lets see both implementation in a single program with 2 differnt methods.

Example's:

array[] = { 11, 12, 13, 14, 15, 16, 17, 18 }
loopValue = 14
Here LinkedList created with loop from 14 to 18

Output: Loop present


array[] = { 1,2,3,4,5,6,7,8,9}
loopValue = 1
Here LinkedList created with loop from 1 to 9

Output: Loop present


array[] = { 10,20,30,40,50,60,70,90,100 }
loopValue = 25
Here LinkedList created and we don't have any node with value 25.

Output: Loop NOT present


import java.util.HashSet;

class NODE {

 int data;
 NODE next = null;

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

public class MyLinkedList {
 
 public static void main(String[] args) {

  int array[] = new int[] { 11, 12, 13, 14, 15, 16, 17, 18 };
  int loopValue = 14;

  //int array[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  //int loopValue = 1;

  //int array[] = new int[] { 10, 20, 30, 40, 50, 60, 70, 90, 100 };
  //int loopValue = 25;

  MyLinkedList obj = new MyLinkedList();

  // Create linkedlist based all array values
  NODE start = obj.createLinkedList(array, loopValue);

  String output1 = obj.findLoopUsingHashSet(start);
  String output2 = obj.findLoopUsing2Pointers(start);

  System.out.println("Using HashSet    : "+output1);
  System.out.println("Using 2 pointers : "+output2);

 }

 /*
  * Create LinkedList and return the start pointer/node
  */
 public NODE createLinkedList(int[] array, int loopValue) {

  NODE start = null;
  NODE tmp = null;

  // Pointer to hold the loop start node
  NODE linkNode = null;

  for (int i : array) {

   tmp = new NODE(i);

   if (start == null) {
    start = tmp;
   } else {
    NODE mover = start;
    while (mover.next != null) {
     mover = mover.next;
    }
    mover.next = tmp;
   }

   // pointer of the node where loop starts
   if (i == loopValue) {
    linkNode = tmp;
   }
  }

  // Create loop from last node to linknode which has loopValue.
  if (linkNode != null) {
   tmp.next = linkNode;
  }

  return start;
 }

 public String findLoopUsingHashSet(NODE start) {

  HashSet<NODE> hs = new HashSet<NODE>();

  while (start != null) {
   if (hs.contains(start))
    return "Loop present";

   hs.add(start);
   start = start.next;
  }
  return "Loop NOT present";
 }
 
 public String findLoopUsing2Pointers(NODE start) {
  
  NODE first = start, second = start;
  while(second != null && second.next != null && second.next.next != null) {
   first = first.next;
   second = second.next.next;
   if(first == second) 
    return "Loop present";
  }
  return "Loop NOT present";
 }
}


OUTPUT:


Using HashSet    : Loop present
Using 2 pointers : Loop present

How to create simple and easy singly LinkedList in Java

Lets see simple Java code to create custom singly LinkedList and maintaining the same order. Also lets traverse the LinkedList and make sure the LinkedList created properly or not. Here we have class called NODE to store the node details like data and next link. MyLinkedList class used to create LinkedList and to print all the values in LinkedList by traversing all nodes from start to end.

How to create simple and easy singly LinkedList in Java



class NODE {

 int data;
 NODE next = null;

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

public class MyLinkedList {

 public static void main(String[] args) {

  int array[] = new int[] { 11, 12, 13, 14, 15, 16, 17, 18 };

  MyLinkedList obj = new MyLinkedList();
  
  //Create linkedlist based all array values
  NODE start = obj.createLinkedList(array);
  
  //print all the values in linkedlist
  obj.traverseLinkedList(start);
 }

 /*
  * Create LinkedList and return the start pointer/node
  */
 public NODE createLinkedList(int[] array) {

  NODE start = null;

  for (int i : array) {

   NODE tmp = new NODE(i);

   if (start == null) {
    start = tmp;
   } else {
    NODE mover = start;
    while (mover.next != null) {
     mover = mover.next;
    }
    mover.next = tmp;
   }
  }
  return start;
 }

 /*
  * Print/traverse the linkedlist all values 
  */
 public void traverseLinkedList(NODE start) {
  while (start != null) {
   System.out.println(start.data);
   start = start.next;
  }
 }
}


OUTPUT:


11
12
13
14
15
16
17
18

Do you know, How to reverse a number using stack?

 
Given a number, write a program to reverse this number using stack operations like push(), and pop() in Java. For example

Do you know, How to reverse a number using stack?

Input: 123456
Output: 654321
Input: 900
Output: 9
Lets see simple java program to reverse a number using stack operation 

import java.util.Stack;

public class ReverseNumber {

 public static void main(String[] args) {
  
  int number = 123456;
  
  System.out.println(reverseNum(number));
 }
 
 public static int reverseNum(int number) {
  Stack<Integer> stack = new Stack<Integer>();
  int counter = 1;
  while(number >0) {
   stack.push(number%10);
   number = number/10;
  }
  number = 0;
  while(stack.size() > 0) {
   number = number + (stack.pop() * counter);
   counter *= 10;
  }
  return number;
 }
}
OUTPUT:

654321

Cool !!! How to find the 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.


Find diameter of a Binary Tree using Java

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

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, 

Inorder Predecessor and Successor of Binary Search Tree

In a given Binary Search Tree need to find the predecessor and Successor of a given node.

What is Predecessor and Successor ?

In a given Binary Search Tree highest element on the left subtree is the Predecessor and lowest element on the right subtree is the Successor of the given node. For example in a below given binary search tree if we need to find Predecessor and Successor of node 28

Inorder Predecessor and Successor of Binary Search Tree


then, node 20 will be the Predecessor and node 36 will be the Successor.

Lets see simple example as how to find Inorder Predecessor and Successor for any given binary tree.


public class PredecessorSuccessor {

 class BST {

  BST left; // Left subtree
  BST right; // Right subtree
  int data; // Element

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

 private int predecessor = -1;
 private int successor = -1;
 private int previous = -1;

 public static void main(String[] args) {

  int val[] = new int[] { 28, 15, 40, 19, 10, 36, 45, 20, 5, 50 };

  int findPreSuc = 28;
  
  PredecessorSuccessor obj = new PredecessorSuccessor();

  BST root = obj.createBST(val);

  obj.getPredecessorSuccessor(root, findPreSuc);
  
  System.out.println("Given node element : "+findPreSuc);
  
  if(obj.predecessor == -1) {
   System.out.println("No Predecessor for the given node ");
  }else {
   System.out.println("Predecessor : " + obj.predecessor);

  }if(obj.successor == -1) {
   System.out.println("No Successor for the given node ");
  }else {
   System.out.println("Successor : " + obj.successor);

  }
 }

 // BST in-order traversal
 public void getPredecessorSuccessor(BST root, int findPreSuc) {

  // Return once we got both Predecessor and Successor
  if (predecessor != -1 && successor != -1) {
   return;
  }

  // Recursive to left subtree
  if (root.left != null) {
   getPredecessorSuccessor(root.left, findPreSuc);
  }

  // Getting Predecessor
  if (root.data == findPreSuc) {
   predecessor = previous;
  }

  // Getting Successor
  if (findPreSuc == previous) {
   successor = root.data;
   previous = root.data;
   return;
  }
  previous = root.data;
  
  // Recursive to right subtree
  if (root.right != null) {
   getPredecessorSuccessor(root.right, findPreSuc);
  }

 }

 public BST createBST(int[] val) {

  BST root = new BST(val[0]); // Root node with 1st element
  BST tmpRoot = root;

  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:


Given node element : 28
Predecessor : 20
Successor : 36