I think its not full binary tree


The solution should be 2^R + 2 ^C because its not going to be a full binary tree.


It is a full binary tree because if you will see the tree closely, both parameters strive to reach m-1 and n-1 respectively, but at a time only one can be incremented. Thus in the most basic case, firstly first parameter will reach n-1, in n-1 iterations and then the second parameter will reach m-1, in m-1 iterations. Thus the total number of iterations would be n-1 + m-1 = n+m-2
Making the complexity O(2^(n+m))


While it true that both parameters r, c eventually reach R-1 and C-1 and it takes R+C-2 calls to increase r and c from 0 to R-1 and C-1 respectively, it doesn’t mean that the tree is a full binary tree. Take for example the path that increases r and never increases c. It will continue to increase r until r = R (so R calls/iterations) and then stop by returning infinity. And so will any other path once one of the parameters reaches R or C respectively. Thus what we’ll get is not a full binary tree, but a full tree until level min(R-1,C-1) and then sort of a shrinking tree (towards path that increased both by 1).


My opinion is the same… is not a full binary tree, but is a binary tree with the height R+C in the worst case, therefore the complexity is indeed O(2^(R+C)).


How do we know it is R+C just because that is the maximum height?

And is worst case the right thing to think about? We know deterministically the number of nodes based on the number R and C, there aren’t any special cases.