Same Tree easy

Problem Statement

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 1:

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

Example 2:

Input: p = [1,2], q = [1,null,2] Output: false

Steps

  1. Base Case: If both p and q are nullptr (empty trees), they are the same, so return true. If only one of them is nullptr, they are different, so return false.

  2. Value Check: Check if the values of the root nodes (p->val and q->val) are different. If they are, the trees are not the same, so return false.

  3. Recursive Calls: Recursively call the isSameTree function for the left subtrees (p->left and q->left) and the right subtrees (p->right and q->right). The trees are the same only if both recursive calls return true.

Explanation

The solution uses recursion to traverse both trees simultaneously. The base case handles the situation where either tree is empty. The value check ensures that the root nodes match. The recursive calls ensure that the structure and values of the subtrees are also identical. If at any point a mismatch is found (either in the root values or in the subtrees), the function immediately returns false. Only if all comparisons pass during the entire traversal will the function return true.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // Base case: both trees are empty
        if (p == nullptr && q == nullptr) {
            return true;
        }
        // Base case: one tree is empty, the other is not
        if (p == nullptr || q == nullptr) {
            return false;
        }
        // Check if the root nodes have the same value
        if (p->val != q->val) {
            return false;
        }
        // Recursively check the left and right subtrees
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be equal to N. In the best case (a balanced tree), H would be logâ‚‚(N).