Is Time Complexity O(N), O(2N) or something else, why?
Please tell me space complexity also for this.
bool solve(Node *root1, Node *root2)
{
if(root1 == NULL && root2 == NULL)
return true;
if((root1 == NULL) || (root2 == NULL))
return false;
if(root1->data != root2->data)
return false;
bool v1 = myfunc(root1->left, root2->left);
bool v2 = myfunc(root1->left, root2->right);
bool v3 = myfunc(root1->right, root2->right);
bool v4 = myfunc(root1->right, root2->left);
return (v1 & v3) | (v2 & v4);
}
bool isIsomorphic(Node *root1, Node *root2)
{
return solve(root1, root2);
}
$$$O(N)$$$ and $$$O(2N)$$$ is the same thing — you should read-up on big-O notation.
Assuming no special tree properties, this particular code is quadratic and has time complexity of $$$O(N^2)$$$. There are several ways to derive this — the simplest is likely to consider that for every level of the trees, each pair of one node from the first and one node from the second will be checked.