LeetCode: 100. Same Tree

The problem

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example

Input: p = [1,2,3], q = [1,2,3]
Output: true

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

bool inorder(TreeNode* p, TreeNode* q){
    if(p == NULL && q == NULL) return true;
    else if(p == NULL && q != NULL) return false;
    else if(p != NULL && q == NULL) return false;
    else if(p->val != q->val) return false;

    return inorder(p->left, q->left) && inorder(p->right, q->right);
}

bool isSameTree(TreeNode* p, TreeNode* q) {
	return inorder(p, q);
}

This code defines two functions: inorder and isSameTree, both of which are used to determine if two binary trees are the same.

bool inorder(TreeNode* p, TreeNode* q) {

• The inorder function takes two pointers to TreeNode objects, p and q, as input and returns a boolean value (true or false).
• It aims to perform an in-order traversal of two binary trees simultaneously while comparing their corresponding nodes.

if (p == NULL && q == NULL) return true;

• This is the base case for the recursion. It checks if both p and q are NULL, meaning we've reached the end of both trees, and returns true to indicate that the traversal so far has been equal.

else if (p == NULL && q != NULL) return false;4. else if (p != NULL && q == NULL) return false;

• These two conditions handle the case where one of the nodes is NULL while the other is not, indicating a mismatch in the tree structures. In this case, the function returns false as the trees are not the same.

else if (p->val != q->val) return false;

• If both p and q are not NULL but have different values, it means the nodes at the current positions in the two trees are not the same. In this case, the function returns false.

return inorder(p->left, q->left) && inorder(p->right, q->right);

• This line is where the recursion happens. It recursively calls the inorder function on the left subtrees and right subtrees of the input trees p and q. It uses the logical AND (&&) operator to combine the results of these recursive calls.
• This ensures that both the left subtrees and right subtrees of the trees p and q must be the same for the entire trees to be considered the same.

bool isSameTree(TreeNode* p, TreeNode* q) {

• The isSameTree function simply calls the inorder function with the input trees p and q, which initiates the comparison process.

Overall, these functions work together to determine if two binary trees (p and q) are the same by performing an in-order traversal and comparing corresponding nodes.