LeetCode 100: Same Tree Explained with Recursive DFS in C++

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original LeetCode page.

Article Summary

In this problem, we determine whether two binary trees are exactly the same. Equality requires more than containing the same values: every value must appear at the same structural position in both trees.

The natural solution is a synchronized recursive depth-first search. At each step, we compare the two nodes occupying the same position, then recursively compare their left subtrees and right subtrees.

This problem teaches an important binary-tree pattern: when comparing two trees, traverse them together rather than processing them independently.

Original Problem and Credit

This article is based on the LeetCode problem “Same Tree.”

• Original problem: https://leetcode.com/problems/same-tree/description/
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

Original Problem in Simple Terms

You are given the roots of two binary trees, p and q.

Return true only when both trees satisfy these conditions:

1. They have nodes in exactly the same positions.
2. Every pair of corresponding nodes contains the same value.

Otherwise, return false.

A tree is therefore not considered equal merely because it contains the same collection of values. The left-child and right-child relationships must also match.

Constraints

• The number of nodes in both trees is in the range [0, 100].
• Each node value is in the range [-10^4, 10^4].

Real-World Scenario

Imagine a deployment platform that stores a service configuration as a binary decision tree.

Each node contains a numeric configuration code:

• The left child represents one possible decision branch.
• The right child represents another possible decision branch.
• The node value identifies the configuration rule at that position.

Before promoting a replicated configuration to production, the platform needs to verify that the replica is identical to the source configuration.

The verification must confirm both:

• Every rule code is the same.
• Every rule appears in the same left-or-right position.

Two configurations containing the same codes can still behave differently if one code is placed on the left branch in one tree and on the right branch in the other. Therefore, both structure and values must be compared.

This is a hypothetical educational scenario, but it is mathematically equivalent to the original problem.

Examples

Example 1: Identical Trees

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

Both trees have the same root value, the same left-child value, and the same right-child value. Their structures also match.

Example 2: Different Structure

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

Both trees contain the values 1 and 2, but the value 2 appears in different positions:

• In p, it is the left child of 1.
• In q, it is the right child of 1.

The structures are different, so the trees are not the same.

Example 3: Different Values at Matching Positions

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

The trees have the same shape, but their corresponding child values do not match.

Mapping to the Original Problem

The adapted system returns true only when every corresponding configuration rule has the same code and the same structural position. This is exactly the condition required by the original problem.

Solution Intuition

Compare the Trees at the Same Time

A common first thought is to traverse each tree separately, store the values, and compare the resulting lists. That approach can be dangerous if the traversal representation does not preserve missing children.

For example, these trees contain the same values but are structurally different:

p = [1,2]
q = [1,null,2]

A value-only comparison could lose the fact that 2 is a left child in one tree and a right child in the other.

Instead, compare the two trees simultaneously. Every recursive call receives two node pointers representing the same expected position in the trees.

At each position, there are four meaningful cases.

Case 1: Both Nodes Are Null

p == nullptr && q == nullptr

Both trees are empty at this position, so this position matches.

Return true.

Case 2: Exactly One Node Is Null

p == nullptr || q == nullptr

Because the case where both are null has already been handled, this condition means one tree contains a node while the other does not.

Their structures differ, so return false.

Case 3: The Values Are Different

p->val != q->val

Both nodes exist, but they store different values. The trees cannot be identical, so return false.

Case 4: The Current Nodes Match

When both nodes exist and contain the same value, the current position is valid. However, the entire trees are equal only if both corresponding subtree pairs are also equal:

isSameTree(p->left, q->left) &&
isSameTree(p->right, q->right)

The logical AND operator is essential. Both the left comparison and the right comparison must succeed.

Recognizing the Pattern

This problem belongs to the simultaneous tree traversal pattern.

Use this pattern when a problem asks whether two trees:

• Are identical.
• Are mirror images.
• Have matching subtrees.
• Satisfy a relationship between corresponding nodes.

The key idea is to pass one node from each tree into the recursive function and compare the pair before continuing.

Algorithm

1. Receive two node pointers, p and q.
2. If both pointers are nullptr, return true.
3. If exactly one pointer is nullptr, return false.
4. If p->val and q->val are different, return false.
5. Recursively compare p->left with q->left.
6. Recursively compare p->right with q->right.
7. Return true only if both recursive comparisons return true.

Why the Algorithm Works

The main invariant is:

Every call to isSameTree(p, q) determines whether the two subtrees rooted at p and q are identical.

The base cases correctly handle subtree structure:

• If both roots are null, both subtrees are empty and therefore identical.
• If only one root is null, one subtree contains a node where the other does not, so their structures differ.

When both roots exist, the subtrees can be identical only if their root values match. After confirming the root values, the same condition must hold recursively for the corresponding left subtrees and corresponding right subtrees.

Therefore, a call returns true exactly when:

1. The current roots match.
2. The left subtrees match.
3. The right subtrees match.

By applying this rule recursively to every corresponding position, the algorithm returns true if and only if the complete trees are structurally identical and contain equal values at every matching node.

Complexity Analysis

Let n be the number of nodes compared in the worst case. When the trees are identical, this is the number of nodes in either tree.

Time Complexity

O(n)

Each corresponding node pair is processed once. The work performed during one call—null checks, one value comparison, and pointer access—is constant time.

If a mismatch is found early, the function may return before visiting every node. However, in the worst case, the trees are identical or differ only near the end of the traversal, so all n nodes must be examined.

Space Complexity

O(h)

Here, h is the height of the trees. The auxiliary space comes from the recursive call stack.

• For a balanced tree, h = O(log n).
• For a completely skewed tree, h = O(n).

Therefore, the worst-case auxiliary space complexity is O(n).

C++ Solution: Recursive Depth-First Search

/**
 * 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) {
        // Both trees are empty at this position.
        if (p == nullptr && q == nullptr) {
            return true;
        }

        // One tree has a node here, but the other does not.
        if (p == nullptr || q == nullptr) {
            return false;
        }

        // The nodes occupy the same position but store different values.
        if (p->val != q->val) {
            return false;
        }

        // Both corresponding subtree pairs must also be identical.
        return isSameTree(p->left, q->left) &&
               isSameTree(p->right, q->right);
    }
};

Walkthrough

Consider the third example:

p = [1,2,1]
q = [1,1,2]

The recursive comparison proceeds as follows:

The algorithm does not need to compare the remaining right subtrees after the left mismatch. C++ short-circuit evaluation stops the && expression as soon as its left side returns false.

Common Mistakes

Comparing Only Node Values

Checking only p->val == q->val verifies the current nodes, not the complete trees. The left and right subtrees must also be compared.

Accessing a Null Pointer

The code must perform null checks before reading p->val or q->val. Accessing a member through nullptr causes undefined behavior.

Treating One Null Node as a Match

A missing node matches only another missing node. If one pointer is null and the other is not, the structures differ.

Comparing the Wrong Child Pairs

The left subtree of p must be compared with the left subtree of q, and the right subtree of p must be compared with the right subtree of q.

Comparing left with right would test a mirror relationship instead of exact equality.

Using OR Instead of AND

This is incorrect:

isSameTree(p->left, q->left) ||
isSameTree(p->right, q->right)

It would accept the trees when only one side matches. Exact equality requires both sides to match, so the correct operator is &&.

Key Takeaways

• Two binary trees are equal only when both their structure and corresponding values match.
• Comparing two trees simultaneously preserves the relationship between matching positions.
• Null-pointer cases should be handled before node values are accessed.
• Recursive DFS fits naturally because each tree is defined by its root, left subtree, and right subtree.
• The solution runs in O(n) time and uses O(h) recursive stack space, with O(n) space in the worst case.