Recursive solution in C++ gives TLE, but not in Python


#1

Used the same approach with both C++ and Python

The C++ code -

TreeNode* utility (vector<int> A, int l, int r) {
    if (l <= r) {
        int m = (l + r) / 2;
        TreeNode* rn = (TreeNode *) malloc(sizeof(TreeNode));
        rn->val = A[m];
        rn->left = (l <= m-1) ? utility(A, l, m - 1) : NULL;
        rn->right = (m + 1 <= r) ? utility(A, m + 1, r) : NULL;
        return rn;
    }
    return NULL;
}
TreeNode* Solution::sortedArrayToBST(const vector<int> &A) {
    return utility(A, 0, A.size() - 1);
}

The Python code -

def utility(A, l, r):
    if l <= r:
        m = int((l + r) / 2)
        t = TreeNode(A[m])
        t.left = utility(A, l, m - 1)
        t.right = utility(A, m + 1, r)
        return t
    return None

class Solution:
    # @param A : tuple of integers
    # @return the root node in the tree
    def sortedArrayToBST(self, A):
        return utility(A, 0, len(A) - 1)

Both versions have similar recursive logic, but the C++ one gives TLE.
Can anyone find any bottleneck in the C++ version?


#2

use const vector A in utility function o/w the vector is copied which makes it TLE


#3

using a const vector solved the issue.


#4

In the utility function, call the vector by reference (so that the vector is not copied many times in recursion) and use const also.