Nov 30, 2013

Display all nested files at given directory location - Recursively display all files from innermost directories

In Java file.list() and file.listFiles() are used to list all File objects (file and directory) at given directory (All Files just one level down to that abstract file path). Suppose we want to list all nested files present at all level with respect to given abstract path.
Consider following E:\\Dir1\\file1.txt , E:\\Dir1\\Dir3\\file3.txt, E:\\Dir1\\file4.txt, E:\\Dir1\\file2.xml , E:\\Dir1\\temp.log - We want to list all files at E:\\Dir1. Output should be : file1.txt, file2.xml, file3.txt, file4.txt.
Below sample program display all files present below the given abstract path:-
package com.devinline.javaio;

import java.io.File;
import java.io.IOException;
import java.util.LinkedList;
import java.util.List;

public class DisplayAllNestedFiles {

 public static void main(String[] args) {
  List<File> fileList = new LinkedList<>();
  File dir = new File("E:\\input");
  fileList = listAllFiles(dir, fileList);
  // Display all files with absolute paths
  for (File file : fileList) {
   try {
    System.out.println(file.getCanonicalPath());
   } catch (IOException e) {
    e.printStackTrace();
   }
  }
 }

 // Recursive call to find File object is file or directory  
 private static List<File> listAllFiles(File dir, List<File> fileList) {
  for (File fileEntry : dir.listFiles()) {
   if (fileEntry.isDirectory()) {
    listAllFiles(fileEntry, fileList);
   } else {
    fileList.add(fileEntry);
   }
  }
  return fileList;
 }

}
======Sample Output========
E:\input\doc\Install_doc.doc
E:\input\EmployeeDST.xml
E:\input\extra\customerLog.json
E:\input\install_doc.pdf
E:\input\trailLog.json
========================
In above program, listAllFiles(File, List) method does looping on the given abstract path "E:\\input" and check if File object is Directory then again call this method again and if it is a file then add it to the list. Once this loop ends, list with all File object is returned and absolute path of each file is displayed.


Nov 26, 2013

Textual description of firstImageUrl

Diaplay Left View of Binary tree in Java

Left view of tree means - nodes which are visible when tree is viewed from left side.And similarly right view of tree is all nodes visible from right side of tree.Consider following binary tree
Left view of tree : [12,23,11,56]

Approach 1:- Using level order traversal
Traverse binary tree in level order and maintain a queue indicating start of node at each level. Here I have used Integer.MAX_VALUE as marker indicating start of new level.
Algorithm:-
1. Insert root and marker in queue, display root as it will be visible from left side.
2. Loop queue until it is empty
      2.1 Remove element from queue and check it is marker. If marker and queue is not empty(last  
            marker of tree) set flag true to display next element from queue.
      2.2 If removed node has left and right child, insert them in queue. Left followed by right child.
      2.3 If flag is set, display removed element and flip flag status
Note:- We are checking queue is empty or not in step 2.1 because when last marker is removed and queue become empty, we do not need to put marker again assuming next level will start.

Sample code:-
public static void leftViewOfTree(Node root) {
 if (root == null)
  return;
 Queue<Node> queue = new LinkedList<>();
 queue.add(root);
 boolean leftFlag = false;
 queue.add(new Node(Integer.MAX_VALUE));
 System.out.println(root.getData() + " ");
 while (!queue.isEmpty()) {
  Node temp = queue.remove();
  if (leftFlag && !queue.isEmpty()) {
   System.out.println(temp.getData());
   leftFlag = false;
  }
  if (temp.getData() == Integer.MAX_VALUE && !queue.isEmpty()) {
   queue.add(new Node(Integer.MAX_VALUE));
   leftFlag = true;
  }
  if (temp != null) {
   if (temp.getLeftChild() != null) {
    queue.add(temp.getLeftChild());
   }
   if (temp.getRightChild() != null) {
    queue.add(temp.getRightChild());
   }
  }
 }

}

Approach 2:- Recursive traversal and using a mapHere we traverse binary tree assuming root at level 0 and maintain a linked Hashmap for storing first node of that level.
Algorithm:-
1. Insert root node in map with key as 0 and node as value.
2. For each node we traverse - mark left child level as currentLevel -1 and for right child as currentLevel -1.
3. Make an entry in map with level value as key, if it already does not exist and traverse recursively left child followed by right child.

Sample code:-
 public static void leftViewRecur(Node root) {
  Map<Integer, Node> map = new LinkedHashMap<>();
  map.put(0, root);
  leftViewRecurUtil(root, 0, map);
  for (Node temp : map.values()) {
   System.out.println(temp.getData());
  }
 }

 private static void leftViewRecurUtil(Node root, int level,
   Map<Integer, Node> map) {
  if (root == null)
   return;
  if (root.getLeftChild() != null) {
   if (map.get(level + 1) == null) {
    map.put(level + 1, root.getLeftChild());
   }
   leftViewRecurUtil(root.getLeftChild(), level + 1, map);
  }
  if (root.getRightChild() != null) {
   if (map.get(level + 1) == null) {
    map.put(level + 1, root.getRightChild());
   }
   leftViewRecurUtil(root.getRightChild(), level + 1, map);
  }
 }

Approach 3:- Recursive traversal and using a map
It is similar to above approach but here we are not maintaining map for storing first node of the given level, we maintain a global variable maxLevel - which indicates current max level reached and for left and right child level is passed as currentLevel + 1.

Algorithm:-
1. Iterate tree recursively left subtree followed by right subtree and pass level as currentLevel+1 .
2. Compare maxLevel with current level
    if maxLevel < levelOfNode , print it as left view node

Sample code:-
public static void leftViewRecurWithLevel(Node root, int level) {
 if (root == null)
  return;
 if (maxLevel < level) {
  System.out.println(root.getData());
  maxLevel = level;
 }
 if (root.getLeftChild() != null) {
  leftViewRecurWithLevel(root.getLeftChild(), level + 1);
 }
 if (root.getRightChild() != null) {
  leftViewRecurWithLevel(root.getRightChild(), level + 1);
 }
}

Complete sample program with all 3 approaches
:-
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class LeftViewOfTree {

 /**
  * devinline.com
  * 
  */
 static private int maxLevel = 0;

 public static void leftViewOfTree(Node root) {
  if (root == null)
   return;
  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  boolean leftFlag = false;
  queue.add(new Node(Integer.MAX_VALUE));
  System.out.println(root.getData() + " ");
  while (!queue.isEmpty()) {
   Node temp = queue.remove();
   if (leftFlag && !queue.isEmpty()) {
    System.out.println(temp.getData());
    leftFlag = false;
   }
   if (temp.getData() == Integer.MAX_VALUE && !queue.isEmpty()) {
    queue.add(new Node(Integer.MAX_VALUE));
    leftFlag = true;
   }
   if (temp != null) {
    if (temp.getLeftChild() != null) {
     queue.add(temp.getLeftChild());
    }
    if (temp.getRightChild() != null) {
     queue.add(temp.getRightChild());
    }
   }
  }

 }

 public static void leftViewRecur(Node root) {
  Map<Integer, Node> map = new LinkedHashMap<Integer, Node>();
  map.put(0, root);
  leftViewRecurUtil(root, 0, map);
  for (Node temp : map.values()) {
   System.out.println(temp.getData());
  }
 }

 private static void leftViewRecurUtil(Node root, int level,
   Map<Integer, Node> map) {
  if (root == null)
   return;
  if (root.getLeftChild() != null) {
   if (map.get(level + 1) == null) {
    map.put(level + 1, root.getLeftChild());
   }
   leftViewRecurUtil(root.getLeftChild(), level + 1, map);
  }
  if (root.getRightChild() != null) {
   if (map.get(level + 1) == null) {
    map.put(level + 1, root.getRightChild());
   }
   leftViewRecurUtil(root.getRightChild(), level + 1, map);
  }
 }

 public static void leftViewRecurWithLevel(Node root, int level) {
  if (root == null)
   return;
  if (maxLevel < level) {
   System.out.println(root.getData());
   maxLevel = level;
  }
  if (root.getLeftChild() != null) {
   leftViewRecurWithLevel(root.getLeftChild(), level + 1);
  }
  if (root.getRightChild() != null) {
   leftViewRecurWithLevel(root.getRightChild(), level + 1);
  }
 }

 public static void rightViewRecur(Node root, int level) {
  if (root == null)
   return;
  if (maxLevel < level) {
   System.out.println(root.getData());
   maxLevel = level;
  }
  if (root.getRightChild() != null) {
   rightViewRecur(root.getRightChild(), level + 1);
  }
  if (root.getLeftChild() != null) {
   rightViewRecur(root.getLeftChild(), level + 1);
  }
 }

 public static void main(String[] args) {
  java.util.Scanner scanner = new java.util.Scanner(System.in);
  System.out.println("Enter input between (1 to 3)");
  int input = scanner.nextInt();
  BinaryTree bt = new BinaryTree();
  Node root = bt.createTree();
  switch (input) {
  case 1:

   leftViewOfTree(root);
   break;
  case 2:
   leftViewRecur(root);

   break;
  case 3:
   leftViewRecurWithLevel(root, 1);
   break;

  default:
   break;
  }

 }

}

class BinaryTree {
 Node root;

 public BinaryTree() {
  root = null;
 }
 public Node createTree() {
  if (root == null) {
   root = new Node(12);
  }
  root.setLeftChild(new Node(23));
  root.setRightChild(new Node(18));
  root.getLeftChild().setLeftChild(new Node(11));
  root.getLeftChild().setRightChild(new Node(43));
  root.getRightChild().setLeftChild(new Node(12));
  root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
  root.getLeftChild().getLeftChild().setRightChild(new Node(78));
  root.getRightChild().getLeftChild().setRightChild(new Node(98));
  root.getRightChild().setRightChild(new Node(99));
  return root;
 }

}

class Node {

 private int data;
 private Node leftChild;
 private Node rightChild;

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

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node getLeftChild() {
  return leftChild;
 }

 public void setLeftChild(Node leftChild) {
  this.leftChild = leftChild;
 }

 public Node getRightChild() {
  return rightChild;
 }

 public void setRightChild(Node rightChild) {
  this.rightChild = rightChild;
 }

}

Sample output:-
====================
>java LeftViewOfTree
Enter input between (1 to 3)
1
12
23
11
56

>java LeftViewOfTree
Enter input between (1 to 3)
2
12
23
11
56

>java LeftViewOfTree
Enter input between (1 to 3)
3
12
23
11
56
====================

Nov 24, 2013

How to create temporary file and automatic cleanup in Java - createTempFile(prefix, suffix, dir) and deleteOnExit()

Sometimes we need to create temporary file in system and need to delete the same automatically. In Java we have a static method (createTempFile(prefix, suffix, dir) ) in File class which creates temporary file and provides facility of automatic clean-up. General syntax for this method is :-
public static File createTempFile(String prefix, String suffix,File directory)
prefix
-  minimum three character string(recommended prefix be a short and meaningful string)
suffix - a extension kind of string(.log,.txt), It may be null then ".tmp" will be used for suffix.Suffix can be without a period operator(.)
directory - an optional argument, if provided temporary file will be created at that location, else temp directory of system will be used. For Unix (\tmp or \var\tmp), for windows(C:\\WINNT\\TEMP- NT4 system or C:\Users\<username>\AppData\Local\Temp\ - for Vista/2008/7/8/2012/10).Refer this for more information about default temporary dir in windows.
Temporary file can be  created in following ways depending on arguments passed :- 
Case 1:- public static File createTempFile(String prefix, String suffix,File directory)- temporary file is created at abstract directory location, with file name <prefix><random#><suffix>

Case 2:-
 public static File createTempFile(String prefix, String suffix) - temporary file is created at system dependent temp directory location, with file name <prefix><random#><suffix>

Case 3:- public static File createTempFile(String prefix, null) - temporary file is created at system dependent temp directory location, with file name <prefix><random#>.tmp  (.tmp is default suffix)

How does automatic clean-up is achieved for temporary file ? :- File class has a method deleteOnExit() which can be used with this temporary file. When JVM shut down gracefully, temporary file will be deleted automatically.

Below sample program creates three temporary files considering all three cases discussed above and do clean up for the same. 

package com.devinline.javaio;

import java.io.File;
import java.io.IOException;

public class TemporaryFileCreation {

 public static void main(String[] args) {
  File tempDir = new File("E:\\logs\\tmp\\");
  try {
   // create temporary file using prefix, suffix and directory
   File tempFile = File.createTempFile("webClickLog", ".txt", tempDir);
   System.out.println("Case 1:Temp file created "
     + tempFile.getAbsolutePath());
   // Automatic temp file clean up with JVM halt
   tempFile.deleteOnExit();

   // Create temporary file using prefix, suffix and default system
   // dependent temp dir
   File tempFile1 = File.createTempFile("webLogin", ".log");
   System.out.println("\nCase 2:Temp file created "
     + tempFile1.getAbsolutePath());
   // Automatic temp file clean up with JVM halt
   tempFile.deleteOnExit();

   // Create temporary file with default suffix(.tmp)and default
   // directory
   File tempFile2 = File.createTempFile("webClickLog", null);
   System.out.println("\nCase 3:Temp file created "
     + tempFile2.getAbsolutePath());
   // Automatic temp file clean up with JVM halt
   tempFile.deleteOnExit();

  } catch (IOException e) {
   e.printStackTrace();
  }

 }

}
=========Sample output===========
Case 1:Temp file created E:\logs\tmp\webClickLog69104232198436172.txt

Case 2:Temp file created C:\Users\nranjan\AppData\Local\Temp\webLogin4842906534820318825.log

Case 3:Temp file created C:\Users\nranjan\AppData\Local\Temp\webClickLog8224675519388746908.tmp
================================

Nov 20, 2013

Find maximum element node in binary tree in Java - Recursive and Iterative

In order to find maximum element in the binary tree we can use recursive post-order and iterative pre-order traversal. Instead of processing it we need check whether value of the given node is greater than current maxNode or not.
Sample code for searching  an element in binary tree in Java - recursive approach 
public Node findMaxInBinaryTreeRecursive(Node root, Node maxNode) {
 Node lMax = null, rMax = null;
 if (root != null) {
  Node lc = root.leftChild;
  Node rc = root.rightChild;
  if (lc != null) {
   lMax = findMaxInBinaryTreeRecursive(lc, maxNode);
  }
  if (rc != null) {
   rMax = findMaxInBinaryTreeRecursive(rc, maxNode);
  }

  if (lMax == null || rMax == null) {
   if (lMax == null && rMax == null) {
    maxNode = root;
   } else if (lMax == null && rMax != null) {
    maxNode = rMax.data > root.data ? rMax : root;
   } else if (lMax != null && rMax == null) {
    maxNode = lMax.data > maxNode.data ? lMax : maxNode;
   }
  } else {
   maxNode = lMax.data > rMax.data ? lMax : rMax;
   maxNode = root.data > maxNode.data ? root : maxNode;
  }

 }
 return maxNode;
}
Explanation:-Traverse binary tree  in post order manner(LDR) - first left subtree followed by right subtree and finally compare left, right and root node value and return maximum value out of them.Check if both left and right node and assign maxValue accordingly.

Sample code for searching  an element in binary tree in Java - iterative approach 

public Node findMaxInBinaryTreeIterative(Node root) {
 Node maxNode = root;
 Node temp;
 Stack<Node> stack = new Stack<>();
 stack.push(root);
 if (root != null) {
  while (!stack.isEmpty()) {
   temp = stack.pop();
   if (maxNode.data < temp.data) {
    maxNode = temp;
   }
   Node lc = temp.leftChild;
   Node rc = temp.rightChild;
   if (lc != null) {
    stack.push(lc);
   }
   if (rc != null) {
    stack.push(rc);
   }
  }
 }
 return maxNode;
}
Explanation:- Traverse binary tree in iterative pre-order manner and after popping an element from stack check for whether it's value is greater than current maximum value or not. If greater mark popped node as maximum

Complete sample program -finding maximum element in binary tree in Java (Iterative and Recursive) 

package com.devinline.trees;

import java.util.Stack;

public class FindMaxInBinaryTree {

public Node findMaxInBinaryTreeIterative(Node root) {
 Node maxNode = root;
 Node temp;
 Stack<Node> stack = new Stack<>();
 stack.push(root);
 if (root != null) {
  while (!stack.isEmpty()) {
   temp = stack.pop();
   if (maxNode.data < temp.data) {
    maxNode = temp;
   }
   Node lc = temp.leftChild;
   Node rc = temp.rightChild;
   if (lc != null) {
    stack.push(lc);
   }
   if (rc != null) {
    stack.push(rc);
   }
  }
 }
 return maxNode;
}

public Node findMaxInBinaryTreeRecursive(Node root, Node maxNode) {
 Node lMax = null, rMax = null;
 if (root != null) {
  Node lc = root.leftChild;
  Node rc = root.rightChild;
  if (lc != null) {
   lMax = findMaxInBinaryTreeRecursive(lc, maxNode);
  }
  if (rc != null) {
   rMax = findMaxInBinaryTreeRecursive(rc, maxNode);
  }

  if (lMax == null || rMax == null) {
   if (lMax == null && rMax == null) {
    maxNode = root;
   } else if (lMax == null && rMax != null) {
    maxNode = rMax.data > root.data ? rMax : root;
   } else if (lMax != null && rMax == null) {
    maxNode = lMax.data > maxNode.data ? lMax : maxNode;
   }
  } else {
   maxNode = lMax.data > rMax.data ? lMax : rMax;
   maxNode = root.data > maxNode.data ? root : maxNode;
  }

 }
 return maxNode;
}

 class Node {
  private int data;
  private Node leftChild;
  private Node rightChild;

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

  public int getData() {
   return data;
  }

  public void setData(int data) {
   this.data = data;
  }

  public Node getLeftChild() {
   return leftChild;
  }

  public void setLeftChild(Node leftChild) {
   this.leftChild = leftChild;
  }

  public Node getRightChild() {
   return rightChild;
  }

  public void setRightChild(Node rightChild) {
   this.rightChild = rightChild;
  }
 }

 class BinaryTree {
  Node root;

  public BinaryTree() {
   root = null;
  }

  public Node createTree() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(23));
   root.setRightChild(new Node(18));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(45));
   root.getRightChild().setLeftChild(new Node(123));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(563));
   root.getLeftChild().getLeftChild().setRightChild(new Node(78));
   root.getRightChild().getLeftChild().setRightChild(new Node(234));
   root.getRightChild().getLeftChild().getRightChild()
     .setRightChild(new Node(48));
   return root;
  }
 }

 public static void main(String[] args) {
  FindMaxInBinaryTree itrObj = new FindMaxInBinaryTree();
  Node root = itrObj.new BinaryTree().createTree();
  Node node = itrObj.findMaxInBinaryTreeIterative(root);
  System.out.println("Iterative preorder traversal:-  " + node.data);
  Node max1 = itrObj.findMaxInBinaryTreeRecursive(root, itrObj.new Node(
    Integer.MIN_VALUE));
  System.out.println("Rec preorder traversal:-  " + max1.data);
 }

}
=======Sample output========
Iterative preorder traversal:-  563
Rec preorder traversal:-  563
=========================