Same Tree Solution Explained – Step-by-Step

Data Structures / Tree

Same Tree

Easy

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

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

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

Explanation

The most intuitive approach to solve this problem is using recursion. The key insight is that two trees are identical if and only if:

Both trees are null (empty trees are identical)
Both trees have the same root value, AND their left subtrees are identical, AND their right subtrees are identical

We recursively check each pair of corresponding nodes. If at any point we find a mismatch (different values or one is null while the other isn't), we return false.

The algorithm naturally handles all cases:

Both nodes are null → return true
One node is null, the other isn't → return false
Both nodes have different values → return false
Both nodes have same value → recursively check left and right subtrees

Idea Map

Start: Check nodes p and q

Are both null?

Yes → return true

No → continue

Is exactly one null?

Yes → return false

No → continue

Are values p.val and q.val equal?

No → return false

Yes → recurse

Return isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right)

End

Complexity Analysis

Time Complexity

O(n) - We visit each node exactly once, where n is the number of nodes in the smaller tree.

Space Complexity

O(h) - The recursion stack uses space proportional to the height h of the tree. In the worst case (skewed tree), this becomes O(n).

Code


def isSameTree(p, q):
Defines the function `isSameTree` that takes two tree roots `p` and `q` as input.
    if not p and not q:
Base case: if both nodes are None (null), trees are identical at this branch.
        return True
Return True since two empty subtrees are considered the same.
    if not p or not q:
If only one node is None (we know both aren't None from previous check).
        return False
Return False because one tree has a node where the other doesn't.
    if p.val != q.val:
Check if the values of current nodes are different.
        return False
Return False because nodes have different values.
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
Recursively check if both left subtrees AND right subtrees are identical.


public boolean isSameTree(TreeNode p, TreeNode q) {
Defines the method `isSameTree` that takes two TreeNode roots `p` and `q` as input.
    if (p == null && q == null) {
Base case: if both nodes are null, trees are identical at this branch.
        return true;
Return true since two empty subtrees are considered the same.
    }
End of the first if block.
    if (p == null || q == null) {
If only one node is null (we know both aren't null from previous check).
        return false;
Return false because one tree has a node where the other doesn't.
    }
End of the second if block.
    if (p.val != q.val) {
Check if the values of current nodes are different.
        return false;
Return false because nodes have different values.
    }
End of the third if block.
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
Recursively check if both left subtrees AND right subtrees are identical.
}
End of the method.


bool isSameTree(TreeNode* p, TreeNode* q) {
Defines the function `isSameTree` that takes two TreeNode pointers `p` and `q` as input.
    if (p == nullptr && q == nullptr) {
Base case: if both nodes are nullptr, trees are identical at this branch.
        return true;
Return true since two empty subtrees are considered the same.
    }
End of the first if block.
    if (p == nullptr || q == nullptr) {
If only one node is nullptr (we know both aren't nullptr from previous check).
        return false;
Return false because one tree has a node where the other doesn't.
    }
End of the second if block.
    if (p->val != q->val) {
Check if the values of current nodes are different (using arrow operator for pointers).
        return false;
Return false because nodes have different values.
    }
End of the third if block.
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
Recursively check if both left subtrees AND right subtrees are identical.
}
End of the function.

Edge Cases & Common Mistakes

⚠️

Order of conditions matters

Always check if both are null first, then if either is null. Checking `p == null || q == null` first would return false even when both are null.

💡

Short-circuit evaluation

The `&&` operator short-circuits: if the left subtree comparison returns false, the right subtree won't be checked. This is an optimization.

✓

Trees with different structures

The recursive approach naturally handles structural differences - if one tree has a node where the other doesn't, the null check catches it.

🔄

Alternative: Iterative approach

You can also solve this iteratively using a queue (BFS) or stack (DFS) to compare nodes level by level or depth by depth.

Deep Dive: Tree Comparison

Tree comparison is a fundamental operation in many algorithms. Understanding how to traverse and compare trees recursively is essential for more complex problems like subtree checking, tree serialization, and finding common ancestors.

Learn more about tree comparison →

account_tree

Disclaimer: This problem is for educational purposes. Practice the 'Same Tree' problem on LeetCode.

AlgoExplained.dev