Same tree

Practice here

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.

Recursive Approach#

• Intuition: Two trees are identical if and only if their roots match and their left subtrees are identical and their right subtrees are identical. This recursive definition maps directly to a recursive solution with no extra bookkeeping.
• Mechanics: The base case returns true when both pointers are null (both subtrees are empty). If exactly one is null, or the values differ, false is returned immediately. Otherwise the call short-circuits on the left subtree first, avoiding the right-subtree call if the left already fails.
• Trade-off: Clean and minimal — O(h) implicit stack space. Short-circuit evaluation means mismatches near the top exit early. Stack depth can reach O(n) for a fully skewed tree.

/**
 * 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) {
        if(!p && !q)
            return true;
        if(!p || !q)
            return false;

        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

Time Complexity: O(n)

Space Complexity: O(h), Recursion stack height = height of the tree (h)

Iterative Approach#

• Intuition: Instead of relying on the call stack, pairs of corresponding nodes from both trees are compared explicitly using a queue. Enqueuing children as pairs keeps the node correspondence intact throughout the BFS traversal.
• Mechanics: The queue holds (node1, node2) pairs. For each pair: skip if both null, fail if exactly one is null or values differ, otherwise enqueue both left children as a pair and both right children as a pair. The trees are identical if the queue empties without any mismatch.
• Trade-off: Avoids recursion and potential stack overflow on deep trees. The queue holds at most O(w) pairs (w = max level width), which can be O(n) for wide trees — similar asymptotically to the recursive O(h) on balanced trees but potentially larger on wide ones.

/**
 * 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) {

        queue<pair<TreeNode*, TreeNode*>> qu;
        qu.push({p,q});

        while(!qu.empty())
        {
            auto [node1, node2] = qu.front();
            qu.pop();

            if(!node1 && !node2)
                continue;

            if(!node1 || !node2 || node1->val != node2->val)
                return false;

            qu.push({node1->left, node2->left});
            qu.push({node1->right, node2->right});
        }

        return true;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)