In pseudocode, you are to write a divide-and-conquer algorithm that checks if two input binary trees are isomorphic. Two trees are isomorphic if they have the same shape and same labels at each corresponding node. (a) An incomplete sketch of the algorithm is given below. Fill-in the missing parts and return the full algorithm. The notation is as follows. If T is a root reference, its left and right children are respectively denoted with T->left and T->right. The label of T is T->label. isIsomorphic ( P, ____) { if( P = null & _______) { return true } if( } 11 Q = null) { return false
In pseudocode, you are to write a divide-and-conquer algorithm that checks if two input binary trees are isomorphic. Two trees are isomorphic if they have the same shape and same labels at each corresponding node. (a) An incomplete sketch of the algorithm is given below. Fill-in the missing parts and return the full algorithm. The notation is as follows. If T is a root reference, its left and right children are respectively denoted with T->left and T->right. The label of T is T->label. isIsomorphic ( P, ____) { if( P = null & _______) { return true } if( } 11 Q = null) { return false
Related questions
Question
Transcribed Image Text:### Isomorphic Binary Trees
In pseudocode, you are to write a divide-and-conquer algorithm that checks if two input binary trees are isomorphic. Two trees are isomorphic if they have the same shape and the same labels at each corresponding node.
#### (a)
An incomplete sketch of the algorithm is given below. Fill in the missing parts and return the full algorithm.
The notation is as follows: If T is a root reference, its left and right children are respectively denoted with T->left and T->right. The label of T is T->label.
```cpp
isIsomorphic( P, Q ) {
if ( P == null && Q == null ) {
return true;
}
if ( P == null || Q == null ) {
return false;
}
if ( P->label != Q->label ) {
return false;
}
return (isIsomorphic(P->left, Q->left)
&& isIsomorphic(P->right, Q->right)
|| (isIsomorphic(P->left, Q->right)
&& isIsomorphic(P->right, Q->left)));
}
```
#### Explanation of Pseudocode:
1. The function `isIsomorphic(P, Q)` checks if trees rooted at nodes P and Q are isomorphic.
2. It first checks whether both trees are null, in which case they are trivially isomorphic.
3. If one tree is null and the other is not, they cannot be isomorphic.
4. It then checks if the labels of the root nodes of both trees are the same.
5. The algorithm proceeds to check if the left subtree of P is isomorphic to the left subtree of Q and if the right subtree of P is isomorphic to the right subtree of Q. Alternatively, it checks if the left subtree of P is isomorphic to the right subtree of Q and the right subtree of P is isomorphic to the left subtree of Q.
#### (b)
Write down the recurrence expressing the complexity of the algorithm.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps
