Problem

Given the roots p and q of two binary trees, determine whether the trees are identical. Two tree are identical if they have the same structure and every corresponding node has the same value.

Examples

• 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

• Example 3

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

Constraints

• Number of nodes in each tree: 0 to 100
• Node values: -10^4 to 10^4

Approach

The task reduces to checking, for every corresponding position in the two trees, that:

• Both position are empty, or
• Both exist and have equal values, and their left subtrees match and their right subtrees match.

Two common strategies work well here:

• Depth-first search (DFS) via recursino: directly mirrors the definition above.
• Breadth-first search (BFS) using a queue of node pairs: iterative compare corresponding nodes level by level.

Time complexity for both approaches is O(n), where n is the number of nodes visited (up to the total nodes across the trees). Space complexity is O(h) for recursion (h = tree height) or O(w) for BFS (w = max width).

Implementations

C++

DFS (recursive)

/**
 * 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* a, TreeNode* b) {
        if (a == b) return true;            // covers both nullptr
        if (!a || !b) return false;
        if (a->val != b->val) return false;
        return isSameTree(a->left, b->left) && isSameTree(a->right, b->right);
    }
};

BFS (single queue of pairs)

#include <queue>
#include <utility>

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        std::queue<std::pair<TreeNode*, TreeNode*>> todo;
        todo.emplace(p, q);
        while (!todo.empty()) {
            auto [x, y] = todo.front();
            todo.pop();
            if (x == y) continue;            // both null or same pointer
            if (!x || !y) return false;      // only one is null
            if (x->val != y->val) return false;
            todo.emplace(x->left, y->left);
            todo.emplace(x->right, y->right);
        }
        return true;
    }
};

Python

DFS (recursive)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSameTree(self, p: 'TreeNode', q: 'TreeNode') -> bool:
        def same(a, b) -> bool:
            if a is b:
                return True
            if not a or not b:
                return False
            return a.val == b.val and same(a.left, b.left) and same(a.right, b.right)
        return same(p, q)

BFS (single deque of node pairs)

from collections import deque

class Solution:
    def isSameTree(self, p: 'TreeNode', q: 'TreeNode') -> bool:
        dq = deque([(p, q)])
        while dq:
            a, b = dq.popleft()
            if a is b:
                continue
            if not a or not b:
                return False
            if a.val != b.val:
                return False
            dq.append((a.left, b.left))
            dq.append((a.right, b.right))
        return True