Pages
Showing posts with label Data Structure. Show all posts
Showing posts with label Data Structure. Show all posts

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


N'th node from the end of a Linked List

 
Need to find the N'th node from the end of Singly Linked List. Since its singly linked we can't traverse bidirectional and important condition is to traverse only once from start to end of the Linked List. Suppose if the length of Linked List is less than N then return -1.

Solution:
> Use 2 pointers where 1st pointer will be traversing from start to end and 2nd pointer will be starting when 1st pointer reaches N'th node.
> In such a way that when 1st pointer reaches the last node in Linked List 2nd pointer will be placed in the N'th node from last.

N'th node from the end of a Linked List


Let see simple Java code to implement LinkedList and to find the N'th node from last just by traversing only once.


public class FindLLNode {

 class LinkedList {
  int data;
  LinkedList next;

  public LinkedList(int data) {
   this.data = data;
   this.next = null;
  }
 }

 public static void main(String[] args) {

  int val[] = new int[] { 23, 7, 10, 45, 9, 11 };

  int findNode = 3;

  FindLLNode obj = new FindLLNode();

  LinkedList start = obj.createLinkedList(val);

  int nthNodeVal = obj.findLLNode(start, findNode);

  System.out.println("nth Node Value from last : " + nthNodeVal);
 }

 private LinkedList createLinkedList(int[] val) {
  LinkedList start = null, temp = null;
  for (int i : val) {

   LinkedList node = new LinkedList(i);
   if (start == null) {
    start = temp = node;
   } else {
    temp.next = node;
    temp = temp.next;
   }
  }
  return start;
 }

 private int findLLNode(LinkedList start, int findNode) {

  LinkedList p1 = start, p2 = start;
  int i = 0;
  boolean flag = false;
  while (p1 != null) {
   if (i >= findNode) {
    p2 = p2.next;
    flag = true;
   }
   p1 = p1.next;
   i++;
  }
  if (!flag)
   return -1;
  return p2.data;
 }
}


OUTPUT:


3rd Node Value from last : 45

Convert a Binary Tree into its Mirror Tree

 
Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged as given below example.
Mirroring Binary Tree

 
public class MirroringBinaryTree {

 class NODE {

  int data;
  NODE left;
  NODE right;

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

 public static void main(String[] args) {

  MirroringBinaryTree obj = new MirroringBinaryTree();

  int val[] = new int[] { 23, 34, 12, 10, 36, 35, 40, 55 };

  NODE root = obj.createBinaryTree(val);

  System.out.print("\n\n INORDER ::::::: ");
  obj.inOrderTraversal(root);

  root = obj.mirror(root);

  System.out.print("\n\n INORDER AFTER MIRROR::::::: ");
  obj.inOrderTraversal(root);
 }

 /*
  * Mirror the binary tree
  */
 public NODE mirror(NODE node) {
  if (node == null)
   return node;

  NODE left = mirror(node.left);
  NODE right = mirror(node.right);

  /* swap left and right pointers */
  node.left = right;
  node.right = left;

  return node;
 }

 /*
  *  BST in-order traversal
  */
 public void inOrderTraversal(NODE root) {

  if (root.left != null) {
   inOrderTraversal(root.left);
  }

  System.out.print(root.data + ", ");

  if (root.right != null) {
   inOrderTraversal(root.right);
  }
 }

 /*
  * Create binary tree by given array
  */
 public NODE createBinaryTree(int val[]) {
  NODE root = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (root == null) {
    root = tmp;
   } else {
    NODE lastNode = getLastNode(root, i);
    if (i > lastNode.data) {
     lastNode.right = tmp;
    } else {
     lastNode.left = tmp;
    }
   }
  }
  return root;
 }

 /*
  * Get parent node the join current node
  */
 public NODE getLastNode(NODE 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:

 
 INORDER ::::::: 10, 12, 23, 34, 35, 36, 40, 55, 

 INORDER AFTER MIRROR::::::: 55, 40, 36, 35, 34, 23, 12, 10,

Find the middle node of a given linked list

 
Given a singly linked list, find the middle NODE of the linked list. For example, if given linked list is 1->2->3->4->5 then output should be 3.
If there are even nodes, then there would be two middle nodes, we need to print second middle element. For example, if given linked list is 1->2->3->4->5->6 then output should be 4.
CONDITION:
  • Need to traverse the linked list only once. 


Find middle node of a given linked list



public class MiddleNode {

 class NODE {
  
  int data;
  NODE next;

  public NODE(int data) {
   this.data = data;
   this.next = null;
  }
 }
 
 public static void main(String[] args) {

  MiddleNode obj = new MiddleNode();

  int val[] = new int[] { 3, 6, 7, 8, 9, 11, 13, 15, 17, 22, 24, 25, 28};
  
  /* Create linked list */
  NODE start = obj.createLinkedList(val);
  
  /* Get middle NODE */
  NODE middleNode = obj.getMiddleNode(start);
  
  System.out.println("MIDDLE NODE : "+middleNode.data);
 }
 
 /*
  * Create linked base based on given array
  */
 public NODE createLinkedList(int val[]) {
  NODE start = null;
  for (int i : val) {
   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;
 }
 
 /*
  * Getting middle NODE just by traversing only once
  */
 public NODE getMiddleNode(NODE start) {
  NODE slow = start, fast = start;
  while(fast.next != null && fast.next.next != null) {
   slow = slow.next;
   fast = fast.next.next;
  }
  if(fast.next != null) {
   slow = slow.next;
  }
  return slow;
 }
}

OUTPUT:


MIDDLE NODE : 13
Get updates in your email box

Complete the form below, and we'll send you our recent update.

Deliver via FeedBurner
© Copyright 2015 Java Discover. Designed by Bloggertheme9 | Distributed By Gooyaabi Templates. Powered by Blogger.