Iterative binary tree traversal

Background

In last post Binary Tree Traversal  we saw recursive method to print the tree. We saw DFS(Depth first search) approach which included pre order, post order and in order traversal and we also saw BFS(Breath first search) approach which includes level order traversal.

In this post we will see an iterative way of implementing the DFS approach. Implementation is very simple and uses stack data structure.

Code :

package Tree;

import java.util.Stack;

/**
 * Created by Aniket on 3/14/14.
 */
public class IterativeTreePrinter {

    public static void printIterativePreOrderTraversal(TreeNode root){

        Stack<TreeNode> stack = new Stack<TreeNode>();

        while(root != null){
            System.out.println("Date : " + root.getData());
            if(root.getRightNode() != null){
                stack.push(root.getRightNode());
            }
            if(root.getLeftNode() != null){
                stack.push(root.getLeftNode());
            }

            if(!stack.isEmpty()){
                root = stack.pop();
            }
            else {
                root = null;
            }
        }
    }


    public static void printIterativeInOrderTraversal(TreeNode root){

        Stack<TreeNode> stack = new Stack<TreeNode>();

        while(!stack.isEmpty() || root != null){
            if(root != null){
                stack.push(root);
                root = root.getLeftNode();
            }
            else {
                root = stack.pop();
                System.out.println("Data : " + root.getData());
                root = root.getRightNode();
            }
        }
    }

    public static void printIterativePostOrder(TreeNode root){

        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode peekNode = null;
        TreeNode lastVisitedNode = null;

        while(!stack.isEmpty() || root != null){

            if(root != null){
                stack.push(root);
                root = root.getLeftNode();
            }
            else {
                peekNode = stack.peek();
                if(peekNode.getRightNode() != null && peekNode.getRightNode() != lastVisitedNode){
                    root = peekNode.getRightNode();
                }
                else {
                    stack.pop();
                    System.out.println("Data : " + peekNode.getData());
                    lastVisitedNode = peekNode;
                }

            }


        }
    }

}

Output : 

Output consumes lot of line as I am printing each data in a single line. So I am skipping it in this case. I have tested and verified the code. Output is same as that of recursive method. You can check the output provided in the post( Binary Tree Traversal  ).

Related Links

• Binary Tree Traversal (OSFG)
• DataStructure git repository   
• Print binary tree in Spiral order (OSFG)

Binary Tree Traversal

Binary Tree Traversal

Binary Tree Traversal

Whats new in Java7?

I know it kind of late to write this post considering Java 7 which was a major update and made available to developers on July 28, 2011.  We have seen a lot of updates and patches for it since then. In fact java 8 is due 18 march 2014. However I though it would be a good idea to list down some of the major features introduced in Java 7.

1. Strings in switch statement
   
   From java 7 you can use String in the Switch statements. The switch statement compares the String object in its expression with the expressions associated with each case label as if it were using the String.equals method; consequently, the comparison of String objects in switch statements is case sensitive. The Java compiler generates generally more efficient bytecode from switch statements that use String objects than from chained if-then-else statements.(More on Switch statement)
   
   Example
   
   

       public static void main(String args[]){
   
           System.out.println("Enter your country");
           Scanner scanner = new Scanner(System.in);
           String input = scanner.nextLine();
   
           switch(input){
   
               case "USA" :
                   System.out.println("You are from USA");
                   break;
               case "India" :
                   System.out.println("You are from India");
                   break;
               default :
                   System.out.println("You are from " + input);
           }
       }
   

   
   
   
2. The try-with-resources StatementThe try-with-resources statement is a try statement that declares one or more resources. A resource is as an object that must be closed after the program is finished with it. The try-with-resources statement ensures that each resource is closed at the end of the statement. Any object that implements java.lang.AutoCloseable, which includes all objects which implement java.io.Closeable, can be used as a resource.
   
   Prior to java 7 when this feature was not available programmers use to close the resources in the finally statement . For Example lets say you need to write a function that takes file path as an argument and return first line from that file. Prior to Java 7 you would do
   
   

   static String readFirstLineFromFileWithFinallyBlock(String path) throws IOException {
     BufferedReader br = new BufferedReader(new FileReader(path));
     try {
       return br.readLine();
     } finally {
       if (br != null) br.close();
     }
   }
   

   
   
   but now you can do
   
   

   static String readFirstLineFromFile(String path) throws IOException {
     try (BufferedReader br = new BufferedReader(new FileReader(path))) {
       return br.readLine();
     }
   }
   

   
   Simple and elegant!
   
   Note: A try-with-resources statement can have catch and finally blocks just like an ordinary try statement. In a try-with-resources statement, any catch or finally block is run after the resources declared have been closed.
   
   Note :  The close methods of resources are called in the opposite order of their creation.
   
   Note : In a simple try catch statement if try block (or catch block) throws an Exception and finally block throws an Exception then the Exception from try block is ignored and the one from finally block is thrown.
   
   Note : In Java 7  try with resource statements there is a twist. Now even try-with-resource statement can throw exception. Again if exception is thrown by finally statement then that is the one that will suppress all other exception. If that is not the case - Exception is thrown from try-with-resource statement (during close) and try block then the one from try block get precedence. However of exception is thrown at initialization (in try-with-res block) try block will not even execute.
   
   
3. Catching Multiple Exception Types
   
   In Java SE 7 and later, a single catch block can handle more than one type of exception. This feature can reduce code duplication and lessen the temptation to catch an overly broad exception.
   
   Consider the following example, which contains duplicate code in each of the catch blocks:
   
   

   catch (IOException ex) {
        logger.log(ex);
        throw ex;
   catch (SQLException ex) {
        logger.log(ex);
        throw ex;
   }
   

   
   
   The following example, which is valid in Java SE 7 and later, eliminates the duplicated code:
   
   

   catch (IOException|SQLException ex) {
       logger.log(ex);
       throw ex;
   }
   

   
   
   The catch clause specifies the types of exceptions that the block can handle, and each exception type is separated with a vertical bar (|).
   
   Note: If a catch block handles more than one exception type, then the catch parameter is implicitly final. In this example, the catch parameter ex is final and therefore you cannot assign any values to it within the catch block.
   
   Note : In a multi-catch block, you cannot combine catch handlers for two exceptions that share a base- and derived-class relationship. You can only combine catch handlers for exceptions that do not share the parent-child relationship between them.
   
   Bytecode generated by compiling a catch block that handles multiple exception types will be smaller (and thus superior) than compiling many catch blocks that handle only one exception type each. A catch block that handles multiple exception types creates no duplication in the bytecode generated by the compiler; the bytecode has no replication of exception handlers.
   
   More details on this part.
4. JDBC
   
   JDBC 4 that comes with Java 7 has following features
   
   
   • You no longer have to explicitly load the driver class using Class.ForName(driver). From JDBC 4 driver class is automatically loaded from the class path.
   • Another addition is the ability to use a try-with-resources statement to automatically close resources of type Connection, ResultSet, and Statement.
   • There is also introduction of the RowSetFactory interface and the RowSetProvider class, which enable you to create all types of row sets supported by your JDBC driver.
5. Interned Strings are allocated in heap area rather that permgen area
   
   In JDK 7, interned strings are no longer allocated in the permanent generation of the Java heap, but are instead allocated in the main part of the Java heap (known as the young and old generations), along with the other objects created by the application. This change will result in more data residing in the main Java heap, and less data in the permanent generation, and thus may require heap sizes to be adjusted. Most applications will see only relatively small differences in heap usage due to this change, but larger applications that load many classes or make heavy use of the String.intern() method will see more significant differences.
6. Garbage-First Collector(G1)
   
   The Garbage-First (G1) garbage collector is fully supported in Oracle JDK 7 update 4 and later releases. The G1 collector is a server-style garbage collector, targeted for multi-processor machines with large memories. It meets garbage collection (GC) pause time goals with high probability, while achieving high throughput. Whole-heap operations, such as global marking, are performed concurrently with the application threads. This prevents interruptions proportional to heap or live-data size.
7. Java File I/O (NIO.2)
   
   In Java 7 new set of I/O APIs were introduced called NIO.2. You can read that in the detailed post - Java File I/O (NIO.2)

Important Links

• How is String in switch statement more efficient then corresponding if-else statement? 
•  How is driver class located in JDBC4
•  Getting Started with the G1 Garbage Collector
• Suppressed exceptions in java 7 (OSFG) 
• Java File I/O (NIO.2) (OSFG)
• Understanding Localization in Java(OSFG) 

HeapSort in Java

Heap Sort sorts an array in place with time complexity O(N log N). Following is the code to do the same

Binary Heap

A binary heap has two following two properties

1. Structural property : All levels except the last are full. Last level is left filled.
2. Heap property : Priority of node is at least as large as it's parent (This is true for min heap but similarly you can have max heap where priority of parent is at least as large as it's children)

Code :

package Sorts;

import java.util.Arrays;

/**
 * Created by Aniket on 3/3/14.
 */
public class HeapSort {

    public int getLeft(int i){
        return 2*i;
    }

    public int getRight(int i){
        return 2*i+1;
    }

    public int getParent(int i){
        return i/2;
    }

    public void maxHeapify(int[]  array, int position){

        int leftPosition = getLeft(position);
        int rightPosition = getRight(position);

        int largest = 0;

        if(leftPosition <= array.length && array[leftPosition-1] > array[position-1]){
            largest = leftPosition;
        }
        else {
            largest = position;
        }
        if(rightPosition <= array.length && array[rightPosition-1] > array[largest-1]){
            largest = rightPosition;
        }

        if(largest != position){
            swap(array,position-1,largest-1);
            maxHeapify(array, largest);
        }
    }

    public void maxHeapifyForSort(int[]  array, int position, int maxPos){

        int leftPosition = getLeft(position);
        int rightPosition = getRight(position);

        int largest = 0;

        if(leftPosition <= maxPos && array[leftPosition-1] > array[position-1]){
            largest = leftPosition;
        }
        else {
            largest = position;
        }
        if(rightPosition <= maxPos && array[rightPosition-1] > array[largest-1]){
            largest = rightPosition;
        }

        if(largest != position){
            swap(array,position-1,largest-1);
            maxHeapifyForSort(array, largest,maxPos);
        }
    }

    public void buildMaxHeap(int[] array){

        for(int i=(array.length)/2;i>0;i--){
            maxHeapify(array,i);
        }

    }

    public void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public void heapSort(int[] array){
        buildMaxHeap(array);
        for(int i=array.length;i>0;i--){
            swap(array,0,i-1);
            maxHeapifyForSort(array,1,i-1);
        }
    }

    public static void main(String args[]){

        int[] array = new int[]{4,1,3,2,16,9,10,14,8,7};
        System.out.println("Original Array : " + Arrays.toString(array));
        //new HeapSort().buildMaxHeap(array);
        new HeapSort().heapSort(array);
        System.out.println("After Sorting Array : " + Arrays.toString(array));


    }

}

Output : 

Original Array : [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
After Sorting Array : [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]

 NOTE: I have shown two similar methods here maxHeapify(int[]  array, int position)
and maxHeapifyForSort(int[]  array, int position, int maxPos) but for sorting you will only need the second one. If your goal is to only create a max heap method one will do just fine. When we go for sort in each iteration we need to decouple indexes from the end so they are the maximum ones and hence we need a limit position to inform heapify function till where it should operate. What heapify does is that each element should have children which are smaller then itself.


NOTE:  Heap sort is an in-place algorithm (in-place algorithm is an algorithm which transforms input using no auxiliary data structure).


Applications :  Heaps are generally used in priority queues ( min or max heap) so that you can retrieve the min or max element in O(1). Insertion will be log(N). It can be used to store realtime data. Lets say to keep score of top 3 people in a game given their scores are changing in realtime.

Related Links

• Heap sort Wiki
• Heap data structure (GeeksForGeeks)
• Learning to Love Heaps (Medium)
• Heap implementation as Priority queue in Java (SO)
• Working with heaps in Python(OSFG)

Infix to Postfix and Prefix conversion

Question :

Question is simply to covert a given infix expression to both prefix as well as postfix notation. The postfix part of the question is picked up from the code chef question --> Transform the Expression . I have simply extended it to output prefix part as well.

Code :

package CodeChef;

import java.util.Stack;

/**
 * Created by Aniket on 2/23/14.
 */
public class PostFixConverter {

    public static void main(String args[]){
        String infix = "((a+b)*(z+x))";
        System.out.println("Postfix : " + printPostFix(infix));
        System.out.println("Prefix : " + printPreFix(infix));

    }

    public static String printPostFix(String str){
        Stack stack = new Stack();
        String postfix = "";
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if(Character.isLetter(c)){
                postfix = postfix + c;
            }
            else if(c == '('){
                continue;
            }
            else if(c == ')'){
                postfix = postfix + ((Character)stack.pop()).toString();
            }
            else{
                stack.push(c);
            }
        }
        return postfix;

    }

    public static String printPreFix(String str){
        Stack stack = new Stack();
        String prefix = "";
        for(int i=str.length()-1;i>=0;i--){
            char c = str.charAt(i);
            if(Character.isLetter(c)){
                prefix = ((Character)c).toString() + prefix;
            }
            else if(c == '('){
                prefix = ((Character)stack.pop()).toString() + prefix;
            }
            else if(c == ')'){
                continue;
            }
            else{
                stack.push(c);
            }
        }
        return prefix;

    }

}

Output :

Postfix : ab+zx+*
Prefix : *+ab+zx

Note :

 Note that the expression provided as input is well bracketed input and hence we are not taking care of ordering. If the question asks for ordering then you need to take care of that as well. For example if infix expression in a+b*c answer(post fix) would be abc*+ and not ab+c*.

MCQ #14

Question : 

There are two code snippets given below. You have to predict output for both.

First :

String str1="str";
String str2="ing";
String concat=str1+str2;

System.out.println(concat=="string");

Second :

final String str1="str";
final String str2="ing";
String concat=str1+str2;

System.out.println(concat=="string");

In both case answer will be either true or false.

Answer : 

Answer is 1st case is false.

Answer in 2nd case is true.

Explanation :

When Java code is compiled, compiler does some optimizations of it's own. An expression that is know to not change during runtime is know as compile time constant expression. So lets say if you have a String
String concat = "str" + "ing";
after compilation it becomes
String concat = "string";
So if question is framed like how many String instances are created in above java code then the answer is one. String literals are interned. So lets come to our problem

1. (False)In first case Strings are not final. Also as we know String is immutable in nature. Concatenation of two String literals yields a new String instance and hence the answer on comparison would be false.
2. (True)In second case Strings are defined as final. That equivalently means the Strings will not change at runtime and hence they form compile time constant expression. So when the code is compiled concat actually points to "string" literal(which is interned as all String literals are). Now since we are comparing this with another String literal with same content both will point to same String instance in the String pool. So the answer in this case would be true.   

Important Links

1. Difference between using == operator and equals() method in Java
2. Comparing strings with == which are declared final in Java
3. how many java String objects will be created in the statement String s=“abc”+“xyz”