Construct binary tree from inorder and postorder traversal

Question

The problem is taken from here. The tree is guaranteed not to have duplicate elements.

My questions is, instead of creating new arrays leftInOrder, rightInOrder, leftPostOrder, rightPostOrder, I could simply pass the indexes to the same input arrays to the recursive function. Does that help in any way?

Basically, any way Java would pass the entire array by value to the recursive function, creating new arrays and passing them only would reduce the load on the stack. I would like to know if this is the best method.

    import java.util.Arrays;
    public class Solution {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder==null || inorder.length<1)return null;
        int rootVal=postorder[postorder.length-1];
        TreeNode root= new TreeNode(rootVal);

        int mid=0;
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==rootVal){
                mid=i;
                i=inorder.length;
            }
        }

        int leftCount=mid;

        int[] leftInOrder= Arrays.copyOfRange(inorder,0,mid);
        int[] rightInOrder= Arrays.copyOfRange(inorder,mid+1,inorder.length);

        int[] leftPostOrder= Arrays.copyOfRange(postorder,0,leftCount);
        int[] rightPostOrder= Arrays.copyOfRange(postorder,leftCount,postorder.length-1);

        root.left=buildTree(leftInOrder,leftPostOrder);
        root.right=buildTree(rightInOrder,rightPostOrder);

        return root;

    }
}

Answer 1

Before tackling the algorithmic issues of your code, lets start with a review of your coding style.

Use proper spacing and indentation

When reviewing, or coming back to code, the readability of the code is very valuable in order to understand the code and to correctly change it. Two very important aspects of this readability is how you indent your code and where you your new lines.

Lets review the start of your code:

public class Solution {
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
    if(inorder==null || inorder.length<1)return null;
    int rootVal=postorder[postorder.length-1];
    TreeNode root= new TreeNode(rootVal);

    int mid=0;
    for(int i=0;i<inorder.length;i++){
        if(inorder[i]==rootVal){
            mid=i;
            i=inorder.length;
        }
        ...
}
}

I have the following issue with this segment of code:

• The classes Solution and TreeNode are at same indentation – This indicates that this classes are defined side by side, which is not unnatural, but then the Solution class seems to miss its implementation. So given they are not defined side-by-side it seems like a compilation error, until you scan a lot more code and realizes that TreeNode is actually an internal class of Solution.
• TreeNode seems to only have 4 members – The way it is written it seems like it has 4 members, and no constructor or methods. Yet again closer inspection reveals that the last parameter isn't a parameter, but actually a constructor with single inline code block.
• The buildTree appears at same level as class definitions – This kind of seems like you have a third class, next to Solution and TreeNode, but it misses the class keyword and has parameters? Oh shoot, it's a method belonging to TreeNode? No, it belongs to Solution but returns a TreeNode.
• Confusing start of buildTree – Ordinarily a method starts with some declaration of local variables, but your first variable is an if statement hiding an early return. This block uses neither braces nor newlines to indicate this block, and is disguised if you don't have a trained eye.
• Inline statements are too compressed – Adding spaces around operators, and after commas can open up your statements a lot. Compare for(int i=0;i<inorder.length;i++){ to for (int i = 0; i < inorder.length; i++) {. Try to think of the statements as sentences where the different parts are words. ItIsNotVeryEasyToReadWithoutSpaces!

Correcting for all of the above you'll end up with this code:

public class Solution {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length < 1) {
            return null;
        }

        int rootVal = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootVal);
        int mid=0;

        for(int i = 0; i < inorder.length; i++){
            if (inorder[i] == rootVal) {
                mid = i;
                i = inorder.length;
            }
        }
        ...
    }
}

This still has some issues, like it doesn't actually check if postorder is not null or has values. But it shows the increase of readability where the only change I've made is to add spaces, correct indentation and add one set of braces.

Algorithmic considerations

In the text of your question you state that Java would pass the entire array by value, which is not correct. If you read Is Java “pass-by-reference” or “pass-by-value”?, you'll see that when passing arrays it's actually the value of the reference to the array which is passed. This allows for the array to be internally dereferenced (and possibly have the array values changed) within the method it is passed to. (It also allows for you to overwrite the array internally, without affecting the external array, but that is another history. Read the accepted answer to the link carefully, and you'll see the difference)

In other words, your suggestion of passing indices will be a much better solution, than the current one. The current one creates loads of extra arrays which it shuffles around making the space requirement of your code grow exponentially (doubling for each recursion). If you passed indices, you would only require space for the extra tree nodes.

So I would rewrite the buildTree into two separate functions something like:

public TreeNode buildTree(int[] inorder, int[] postorder) {
    return buildTree(inorder, postorder, 0, inorder.length);
}

private TreeNode buildTree(int[] inorder, int[] postorder, int left, int right) {
    ... your revised code here ...
}

I would also strongly consider adding some documentation and comments here and there to further enhance and explain what your code is supposed to do!