Convert a given Binary Tree to Doubly Linked List

Question:

Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.(Taken from GeeksForGeeks)

The idea behind its solution is quite simple and straight.

1.  If left subtree exists, process the left subtree
1. Recursively convert the left subtree to DLL.
2. Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
3. Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
1. Recursively convert the right subtree to DLL.
2. Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
3. Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).

 Solution :

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 29/1/14
 * Time: 5:43 PM
 */
public class BTreeToList {

    private static TreeNode btreeToListUtil(TreeNode root){

        if( root == null) {
            return null;
        }

        if(root.getLeftNode() != null){

            TreeNode leftTreeNode = btreeToListUtil(root.getLeftNode());

            while(leftTreeNode.getRightNode() != null){
                leftTreeNode = leftTreeNode.getRightNode();
            }

            leftTreeNode.setRightNode(root);
            root.setLeftNode(leftTreeNode);

        }


        if(root.getRightNode() != null){

            TreeNode rightTreeNode = btreeToListUtil(root.getRightNode());

            while(rightTreeNode.getLeftNode() != null){
                rightTreeNode = rightTreeNode.getLeftNode();
            }

            rightTreeNode.setLeftNode(root);
            root.setRightNode(rightTreeNode);
        }

        return root;

    }

    public static TreeNode btreeToList(TreeNode root){
         TreeNode head = btreeToListUtil(root);
        while(head.getLeftNode() != null){
            head = head.getLeftNode();
        }

        return head;
    }

    public static void printLL(TreeNode root){

        while(root != null){
            System.out.println("Data : " + root.getData());
            root = root.getRightNode();
        }


    }



    public static void main(String args[]){

        TreeNode root = new TreeNode(10);

        TreeNode l = new TreeNode(12);
        TreeNode r = new TreeNode(15);

        TreeNode ll = new TreeNode(25);
        TreeNode lr = new TreeNode(30);

        TreeNode rl = new TreeNode(36);

        root.setLeftNode(l);
        root.setRightNode(r);

        l.setLeftNode(ll);
        l.setRightNode(lr);

        r.setLeftNode(rl);

        printLL(btreeToList(root));

    }

}

Output :

Data : 25
Data : 12
Data : 30
Data : 10
Data : 36
Data : 15

Program to rotate a matrix by 90 degree clockwise.

Question :

You have to rotate the matrix by 90 degrees.

For example if you have

[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]

output must be

[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4] 

Solution : 

 package Matrices;

import java.util.Arrays;

/**
 * Created by Aniket on 1/26/14.
 */
public class NinetyDegRotator {

    public static int [][] rotate(int [][] matrix){
        int rows = matrix.length;
        int cols = matrix[0].length;
        int [][] rotatedMatrix = new int[rows][cols];
        for(int i =0; i<rows;i++){
            for(int j=0;j<cols;j++){
                rotatedMatrix[i][j] = matrix[cols-j-1][i];
            }
        }
        return rotatedMatrix;
    }

    public static void twoDArrayPrinter(int [][] matrix){

        for(int []array : matrix){
            System.out.println(Arrays.toString(array));
        }

    }

    public static void main(String args[]){

        int [][] matrix = new int[][]{
                {1,2,3,4},
                {5,6,7,8},
                {9,0,1,2},
                {3,4,5,6}
        };

        System.out.println("Original Array : ");
        NinetyDegRotator.twoDArrayPrinter(matrix);
        int [][] rotatedMatrix = ninetyDegRotator.rotate(matrix);
        System.out.println("Rotated Array : ");
        NinetyDegRotator.twoDArrayPrinter(rotatedMatrix);
    }

}

Output :

Original Array :
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 0, 1, 2]
[3, 4, 5, 6]
Rotated Array :
[3, 9, 5, 1]
[4, 0, 6, 2]
[5, 1, 7, 3]
[6, 2, 8, 4]

Note : Above algorithm takes O(N^2) time complexity.

 To make the transformation in place it has to be a square matrix(n*n)

Code :

package Matrices;

/**
 * Created by Aniket on 1/26/14.
 */
public class TransposeCreator {
    public static void inPlaceTranspose(int [][] matrix){

        int rows = matrix.length;
        int cols = matrix[0].length;

        for(int i=0;i<rows;i++){
            for(int j=i+1;j<cols;j++){
                matrix[i][j] = matrix[i][j] + matrix[j][i];
                matrix[j][i] = matrix[i][j] - matrix[j][i];
                matrix[i][j] = matrix[i][j] - matrix[j][i];
            }
        }
    }

    public static int[][] transpose(int[][] matrix){

        int rows = matrix.length;
        int cols = matrix[0].length;

        int[][] transposedMatrix = new int[cols][rows];

        for(int i=0;i<cols;i++){
            for(int j=0;j<rows;j++){
                transposedMatrix[i][j] = matrix[j][i];
            }
        }

        return transposedMatrix;

    }

    public static void inPlaceRowsSwapper(int [][] matrix){
        int rows = matrix.length;
        int cols = matrix[0].length;

        for(int i=0;i<rows;i++){
            for(int j=0;j<cols/2;j++){
                matrix[i][j] = matrix[i][j] + matrix[i][cols-j-1];
                matrix[i][cols-j-1] = matrix[i][j] - matrix[i][cols-j-1];
                matrix[i][j] = matrix[i][j] - matrix[i][cols-j-1];
            }
        }

    }


    public static void main(String args[]){

        int [][] matrix = new int[][]{
                {1,2,3,4},
                {5,6,7,8},
                {9,0,1,2},
                {3,4,5,6}
        };

        System.out.println("Original Array : ");
        NinetyDegRotator.twoDArrayPrinter(matrix);
        System.out.println("Transposed Matrix");
        NinetyDegRotator.twoDArrayPrinter(TransposeCreator.transpose(matrix));
        TransposeCreator.inPlaceTranspose(matrix);
        System.out.println("InPlace Transposed matrix");
        NinetyDegRotator.twoDArrayPrinter(matrix);
        System.out.println("90deg rotation matrix");
        TransposeCreator.inPlaceRowsSwapper(matrix);
        NinetyDegRotator.twoDArrayPrinter(matrix);

    }
}

Output :

Original Array :
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 0, 1, 2]
[3, 4, 5, 6]
Transposed Matrix
[1, 5, 9, 3]
[2, 6, 0, 4]
[3, 7, 1, 5]
[4, 8, 2, 6]
InPlace Transposed matrix
[1, 5, 9, 3]
[2, 6, 0, 4]
[3, 7, 1, 5]
[4, 8, 2, 6]
90deg rotation matrix
[3, 9, 5, 1]
[4, 0, 6, 2]
[5, 1, 7, 3]
[6, 2, 8, 4]

Sum of all the numbers that are formed from root to leaf paths.

Question :

Given a binary tree, where every node value is a Digit from 1-9 .Find the sum of all the numbers which are formed from root to leaf paths.
For example consider the following Binary Tree.

 Solution :

The idea is to do a preorder traversal of the tree. In the preorder traversal, keep track of the value calculated till the current node, let this value be val. For every node, we update the val as val*10 plus node’s data.

Answer is : 632 + 6357 + 6354 + 654 = 13997

 Code :

package Tree;

/**
 * Created by Aniket on 1/24/14.
 */
public class TreePathSummer {

    public static int treePathSum(TreeNode root, int val){

        if(root == null){
            return 0;
        }

        val = val * 10 + root.getData();

        if(root.getLeftNode() == null && root.getRightNode() == null){
            return val;
        }

        return treePathSum(root.getLeftNode(),val) + treePathSum(root.getRightNode(),val);

    }

    public static void main(String args[]){
        TreeNode rooTreeNode = new TreeNode(6);

        TreeNode l = new TreeNode(3);
        TreeNode r = new TreeNode(5);

        TreeNode ll = new TreeNode(2);
        TreeNode lr = new TreeNode(5);

        TreeNode lrl = new TreeNode(7);
        TreeNode lrr = new TreeNode(4);

        TreeNode rr = new TreeNode(4);

        rooTreeNode.setLeftNode(l);
        rooTreeNode.setRightNode(r);

        l.setLeftNode(ll);
        l.setRightNode(lr);

        lr.setLeftNode(lrl);
        lr.setRightNode(lrr);

        r.setRightNode(rr);

        System.out.println("Answer is = " + TreePathSummer.treePathSum(rooTreeNode,0));
    }
}

And the output is as expected

Answer is = 13997

For the java code corresponding to TreeNode data structure refer to the earlier post.

Converting Array to a balanced BST(Binary Search Tree)

Question : 

Given an array you need to convert it into an balanced BST(Binary Search Tree).

Example :

Solution :

Given an array first step would be to sort it. You can probably use quick sort which will take average time O(NlogN) complexity. Once you have sorted you can apply following algorithm to convert it into a balance BST.

1. Get the Middle of the array and make it root.
2. Recursively do same for left half and right half.
   
   1. Get the middle of left half and make it left child of the root created in step 1.
   2. Get the middle of right half and make it right child of the root created in step 1.

TreeNode data structure

package Tree;

/**
 * Created by Aniket on 1/22/14.
 */
public class TreeNode {

    int data;
    TreeNode leftNode;
    TreeNode rightNode;

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

    public TreeNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public TreeNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    public int getData() {
        return data;
    }

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

 Code to transform a sorted array into balance BST.

package Tree;

import java.util.Arrays;

/**
 * Created by Aniket on 1/22/14.
 */
public class ArrayToBST {

    public static TreeNode convert(int[] ar, int start, int end){

        if(start > end)
            return null;

        int mid = start + ((end - start)/2);
        TreeNode root = new TreeNode(ar[mid]);
        root.setLeftNode(convert(ar,start,mid-1));
        root.setRightNode(convert(ar,mid+1,end));

        return root;

    }

    public static void main(String args[]){

        int array[] = new int[]{1,2,3,4,5,6,7};
        System.out.println("Array is : " + Arrays.toString(array));


        System.out.println("BST in pre order : ");
        PrintTree.printPreOrderTraversal(ArrayToBST.convert(array,0,array.length-1));

    }

}

and the output is

Array is : [1, 2, 3, 4, 5, 6, 7]
BST in pre order :
Data : 4
Data : 2
Data : 1
Data : 3
Data : 6
Data : 5
Data : 7


Pre-order traversal is a type of tree traversals. You can take a look at the types and code for each in the previous post on Tree traversal.

Building Java projects with Maven.

In last post we saw what is maven and how do we install it. Now lets create a java project and use maven to build and then  test by running it.

What you will need?

1. Maven installed
2. JDK(6 or higher)
3. IDE(Eclipse/Intellij IDEA) or a text editor(gedit/vim)

Setting up the project

Projects that are to be built by maven must follow a particular directory pattern. For detailed directory structure you can visit their documentation on directory structure.

For our example we are going to create a HelloWorld sample inside a package called hello.

So our directory structure will be something like

So go ahead and create such structure. You can use following command

mkdir -p src/main/java/hello

Now inside hello directory create two java files - HelloWorld.java  and Greeter.java.

Code for them is provided below. For src/main/java/hello/HelloWorld.java

package hello;

public class HelloWorld {
    public static void main(String[] args) {
        Greeter greeter = new Greeter();
        System.out.println(greeter.sayHello());
    }
}

and for src/main/java/hello/Greeter.java

package hello;

public class Greeter {
    public String sayHello() {
        return "Hello world!";
    }
}

Now that Maven is installed, you need to create a Maven project definition. Maven projects are defined with an XML file named pom.xml. Among other things, this file gives the project’s name, version, and dependencies that it has on external libraries.

Note :  This file must be in the project root directory which means in the folder which has src folder.

Create a file named pom.xml at the root of the project and give it the following contents:

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>HelloWorld</groupId>
    <artifactId>gs-maven-initial</artifactId>
    <version>0.1.0</version>
    <packaging>jar</packaging>
</project>

Now you can build your java project using 

mvn compile

This will download your dependencies and compile you java files. Corresponding .class files will be created in a target folder in the projects root folder.

To make the jar file of your project you can use

mvn package

This will create a jar file in the target folder. Now you can run your code with

java -jar PathToYourJarFile

Maven Build lifecycle

compile and package were some of the initial phases of Maven build lifecycle. All of them are listed in the following diagram

For more details on the maven build life cycle phases you can visit their official site.

I am getting Can't execute jar- file: “no main manifest attribute”. What should i do?

That is because you have not told maven while packaging how do you built the project. You need to provide build information withing <build> and </build> tags in the build file. You can add following tag between <project> and </project>.

    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-shade-plugin</artifactId>
                <version>2.1</version>
                <executions>
                    <execution>
                        <phase>package</phase>
                        <goals>
                            <goal>shade</goal>
                        </goals>
                        <configuration>
                            <transformers>
                                <transformer
                                    implementation="org.apache.maven.plugins.shade.resource.ManifestResourceTransformer">
                                    <mainClass>hello.HelloWorld</mainClass>
                                </transformer>
                            </transformers>
                        </configuration>
                    </execution>
                </executions>
            </plugin>
        </plugins>
    </build>

and you are done. By this you essentially say what is your main class so that while executing java knows the entry point from that jar file.

I want to use IDE instead of text editor. How do I import maven projects to my IDE?

Even this is very simple. You can run the following commands in the projects root directory -

• mvn eclipse:eclipse  (For Eclispe IDE)
• mvn idea:idea  (For intellij IDEA IDE)

For example idea command will generate all the required files like .ipr(project file), .iws(workspace file) etc. You can open the file by simply opening this .ipr file in IDEA.

Note : As per Mavens official site mvn idea:idea is obsolete. You can directly do File -> Import project and select pom.xml file.

I am getting "Package name does not correspond to the file path" error after importing project in my IDE.

This is because dash(-) is not allowed in package name and your -DgroupId contained  dash(-) which was used as package name. You can refactor and replace dash(-) with underscores(_) which is legal in a package name.

 Useful Links

• Can't execute jar- file: “no main manifest attribute”
• Building Java Projects with Maven
• Maven + Spring hello world example
• Package name does not correspond to the file path