Construct Tree from given Inorder and Preorder traversals

Problem:
Give two strings representing the inorder and preorder traversals of binary tree, construct the tree.

The key here is that preorder traversal, the first char is the tree root. And then based on that char, find the its position in inorder string, then its left portion of in order string is the left subtree, right portion is the right subtree.

And do it recursively, make it simpler.

public static Node constructTree(String pre, String in){

if(pre.isEmpty())

return null;

if(pre.length() == 1)

return new Node(pre.charAt(0));

Node root = new Node(pre.charAt(0));

String[] ins = splitStringBy(in, pre.charAt(0));

                root.left = constructTree(pre.substring(1, ins[0].length()+1), ins[0]);

root.right = constructTree(pre.substring(ins[0].length()+1), ins[1]);

return root;

}

public static String[] splitStringBy(String str, char root){

String[] re = new String[2];

re[0] = str.substring(0, str.indexOf(root));

re[1] = str.substring(str.indexOf(root)+1);

return re;

}

Find the maximum sum from leaf to root in a binary tree

Given a Binary Tree, find the maximum sum from a leaf to root and return this leaf as well.


The key is from root to leave, add up the node value and pass the sum to the lower levels. 

public static int maxSumFromRootHelper(Node root, int sum){

if(root == null)

return sum;

else{

return Math.max(maxSumFromRootHelper(root.left, root.data + sum),

  maxSumFromRootHelper(root.right, root.data + sum));

}

}

//store the max sum result

static int max_sum = Integer.MIN_VAL;

//store the leaf 

static Node maxNode = null;

public static void findLeaveWithMaxSumFromRoot(Node root, int sum){

if(root == null)

return;

sum = sum + root.data;

if(root.left == null && root.right ==null){

if(sum > max_sum){

max_sum = sum;

maxNode = root;

}

}

else{

findLeaveWithMaxSumFromRoot(root.left, sum);

findLeaveWithMaxSumFromRoot(root.right, sum);

}

} 

divide number and return result in a string

This is a google interview question: 

Divide number and return result in form of a string. e.g 100/3 result should be 33.(3) Here 3 is in brackets because it gets repeated continuously and 5/10 should be 0.5.

Here is my attempt, the key is to doing module and division, also figure out how many 0s are there after decimal point. 

public static String divideToString(int num1, int num2){
    int d = num1/num2;
    int m = num1%num2;
    boolean flag = false;
    Set<Integer> seen = new HashSet<Integer>();
    StringBuilder sb = new StringBuilder();
    sb.append(d);
    while(m!=0){
    if(!flag){
        sb.append(".(");
        flag = true;
    } 

     

    num1 = m*10;
    d = num1/num2;
    m = num1%num2;

       

    if(seen.contains(num1)){
    sb.append(")");
    break;
    }else{
    sb.append(d);  
    seen.add(num1);
    }
    }

   

    return sb.toString();
}