Solution timing out for question: build binary tree from inorder and postorder

Question

I've been grinding leetcode recently and am perplexed on why my solution is timing out when I submit it to Leetcode.

Here is the question:

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/942/

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Here is my solution that times out in one of the test cases:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) {
            return null; // input error
        }
        if (postorder == null || postorder.length == 0) {
            return null; // input error
        }
        if (postorder.length != inorder.length) {
            return null; // input error
        }
        List<Integer> inOrder = new ArrayList<Integer>();
        List<Integer> postOrder = new ArrayList<Integer>();
        for (int i = 0; i < inorder.length; i++) {
            inOrder.add(inorder[i]);
            postOrder.add(postorder[i]);
        }
        return buildBinaryTree(inOrder, postOrder);
    }

    public TreeNode buildBinaryTree(List<Integer> inOrder, List<Integer> postOrder) {
        boolean found = false;
        int root = 0;
        int rootIndex = 0;

        // for given in-order scan the post-order right to left to find the root
        for (int j = postOrder.size() - 1; j >= 0 && !found; j--) {
            root = postOrder.get(j);
            if (inOrder.contains(root)) {
                rootIndex = inOrder.indexOf(root);
                root = inOrder.get(rootIndex);
                found = true;
                break;
            }
        }
        if (found) {
            List<Integer> leftOfRoot = new ArrayList<Integer>();
            List<Integer> rightOfRoot = new ArrayList<Integer>();
            if (rootIndex > 0) {
                leftOfRoot.addAll(inOrder.subList(0, rootIndex));
            }
            if ((rootIndex + 1) < inOrder.size()) {
                rightOfRoot.addAll(inOrder.subList(rootIndex + 1, inOrder.size()));
            }
            TreeNode node = new TreeNode(root);
            node.left = buildBinaryTree(leftOfRoot, postOrder);
            node.right = buildBinaryTree(rightOfRoot, postOrder);
            return node;
        }
        return null;
    }
}

Can anyone help determine why this is happening? I'm thinking it is the Leetcode judge at fault here and my code is fine.

Answer 1

Yes, it would be much faster with arrays. Try this:

public static TreeNode buildTree(int[] inorder, int[] postorder, int start,
        int end) {
    for (int i = postorder.length-1; i >= 0; --i) {
        int root = postorder[i];
        int index = indexOf(inorder, start, end, root);
        if (index >= 0) {
            TreeNode left = index == start
                    ? null
                    : buildTree(inorder, postorder, start, index);
            TreeNode right = index+1 == end
                    ? null
                    : buildTree(inorder, postorder, index+1, end);
            return new TreeNode(root, left, right);
        }
    }
    return null;
}

private static int indexOf(int[] array, int start, int end, int value) {
    for (int i = start; i < end; ++i) {
        if (array[i] == value) {
            return i;
        }
    }
    return -1;
}

Answer 2

Leetcode's judge is probably OK. This code is too casual about nested linear array operations and heap allocations. Creating ArrayLists and calling contains, addAll, subList and indexOf may appear innocuous, but they should all be thought of as extremely expensive operations when inside a recursive function that spawns two child calls in every frame.

Let's unpack the code a bit:

List<Integer> inOrder = new ArrayList<Integer>();
List<Integer> postOrder = new ArrayList<Integer>();
for (int i = 0; i < inorder.length; i++) {
    inOrder.add(inorder[i]);
    postOrder.add(postorder[i]);
}

This is a minor up-front cost but it's an omen of things to come. We've done 2 heap allocations that weren't necessary and walked n. I'd stick to primitive arrays here--no need to allocate objects other than the result nodes. A lookup map for inOrder with value -> index pairs might be useful to allocate if you feel compelled to create a supporting data structure here.

Next, we step into buildBinaryTree. Its structure is basically:

function buildBinaryTree(root) {
    // do some stuff

    if (not base case reached) {
        buildBinaryTree(root.left)
        buildBinaryTree(root.right)
    }
}

This is linear on the number of nodes in the tree, so it's important that // do some stuff is efficient, hopefully constant time. Walking n in this function would give us quadratic complexity.

Next there's

for (int j = postOrder.size() - 1; j >= 0 && !found; j--) {
    root = postOrder.get(j);
    if (inOrder.contains(root)) {
        rootIndex = inOrder.indexOf(root);

This looks bad, but by definition the root is always the last element in a postorder traversal array, so if we keep a pointer to it, we can remove this outer loop. You can use indexOf directly and avoid the contains call since indexOf returns -1 to indicate a failed search.

The code:

if (found) {
    List<Integer> leftOfRoot = new ArrayList<Integer>();
    List<Integer> rightOfRoot = new ArrayList<Integer>();

does more unnecessary heap allocations for every call frame.

Here,

leftOfRoot.addAll(inOrder.subList(0, rootIndex));

Walks the list twice, once to create the sublist and again to add the entire sublist to the ArrayList. Repeat for the right subtree for two full walks on n per frame. Using start and end indices per call frame means you never need to allocate heap memory or copy anything to prepare the next call. Adjust the indices and pass a reference to the same two arrays along the entire time.

I recommend running your code with a profiler to see exactly how much time is spent copying and scanning your ArrayLists. The correct implementation should do at most one walk through one of the lists per call frame to locate root in inOrder. No array copying should be done at all.

With these modifications, you should be able to pass, although wrangling the pointers for this problem is not obvious. A hint that may help is this: recursively process the right subtree before the left.