CODEWITHSUNDEEP
c++
WriteBackCMO
WriteBackCMO

Reputation: 619

timing comparison between max() and ?: operator

I write a function to return the max depth of binary tree.

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == 0) return 0;
        if((root -> left ==0) &&(root->right == 0)) return 1;
        **************
    }
};

I wrote two methods for the ***** part Method1:

else return max((1+maxDepth(root -> left)),(1+maxDepth(root -> right)));

Method2 :

else return (maxDepth(root -> left) > maxDepth(root -> right)) ?
            (maxDepth(root->left) + 1):
            (maxDepth(root->right) + 1);

The second method failed timing check while the first one passes. They look pretty similar to me. Anyone can give some hints why the second method is slower?

Upvotes: 0

Views: 79

Answers (1)

cdhowie
cdhowie

Reputation: 169028

The first approach is similar to:

else {
    auto l = 1 + maxDepth(root -> left);
    auto r = 1 + maxDepth(root -> left);

    return (l > r) ? l : r;
}

Note that maxDepth() is only invoked twice.

In your second approach, maxDepth() is invoked twice in the conditional expression, and is then invoked a third time in either the true-expression or false-expression (depending on the outcome of the conditional). This wastes time recomputing the value.

Depending on the state of the tree, this approach could take anywhere between the same amount of time as the first approach, and twice the amount of time as the first approach.

Upvotes: 3

Related Questions