LeetCode 100 - Same Tree

The problem asks us to determine whether two binary trees are exactly the same. We are given the roots of two binary trees, p and q. A binary tree consists of nodes where each node contains a value and references to a left child and a right child.

leetcodeeasytreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 100

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to determine whether two binary trees are exactly the same.

We are given the roots of two binary trees, p and q. A binary tree consists of nodes where each node contains a value and references to a left child and a right child. The task is to compare these two trees and return true if they are identical, otherwise return false.

To be considered the same, the trees must satisfy two conditions simultaneously:

  1. Their structure must be identical, meaning nodes must appear in the same positions.
  2. The values stored at corresponding nodes must match exactly.

This means that even if both trees contain the same values overall, they are not considered the same if those values appear in different locations.

For example:

  • [1,2,3] and [1,2,3] are the same because every node exists in the same place and has the same value.
  • [1,2] and [1,null,2] are different because the second node appears in different positions, even though the values are similar.
  • [1,2,1] and [1,1,2] are different because corresponding nodes contain different values.

The input consists of two root nodes, p and q, which may each be None (or nil in Go), representing an empty tree. The expected output is a boolean value:

  • true if the trees are structurally identical with matching node values
  • false otherwise

The constraints are relatively small:

  • Each tree contains between 0 and 100 nodes.
  • Node values range from -10^4 to 10^4.

Since the tree size is small, many approaches would work efficiently enough. However, the problem naturally lends itself to a recursive depth-first traversal because trees themselves are recursive structures.

Several edge cases are important to recognize early. Both trees may be empty, which should return true because two empty trees are identical. One tree may be empty while the other is not, which should immediately return false. Trees may have the same values but different shapes, which can easily trick naive solutions that only compare traversal results. Trees may also have matching structure but differing node values at some level.

Approaches

Brute Force Approach

A brute-force way to solve this problem is to serialize both trees into arrays using a traversal order such as preorder or level order, explicitly including null markers for missing children. Once serialized, we compare the two resulting arrays.

For example:

Tree 1: [1,2,null,null,3,null,null]
Tree 2: [1,2,null,null,3,null,null]

If the serialized representations are identical, the trees are the same.

This approach works because including null markers preserves structural information. Without them, different trees could incorrectly appear identical.

However, this method introduces unnecessary extra work and memory overhead. We create complete representations of both trees before comparison, even if a mismatch occurs near the root. In the worst case, we still visit every node and store extra data.

Optimal Approach

The key observation is that we do not need to build any intermediate representation of the trees.

Since binary trees are recursive structures, we can compare them recursively node by node:

  • If both nodes are null, they match.
  • If one node is null and the other is not, the trees differ.
  • If the node values differ, the trees differ.
  • Otherwise, recursively compare the left children and right children.

This works naturally with depth-first search (DFS). At every step, we verify both the current node and its subtrees. The moment a mismatch appears, we immediately stop and return false.

This approach is both clean and efficient because it avoids extra storage and short-circuits as soon as a difference is found.

Approach Time Complexity Space Complexity Notes
Brute Force O(n + m) O(n + m) Serialize both trees and compare arrays
Optimal O(min(n, m)) to O(n + m) O(h) Recursive DFS comparison with early termination

Here, n and m are the number of nodes in the two trees, and h is the tree height.

Algorithm Walkthrough

  1. Start at the roots of both trees.

We begin by comparing p and q. Since the trees must be identical from the root downward, any mismatch here immediately means the answer is false. 2. Check if both nodes are null.

If both current nodes are null, this means both trees are missing a node at the same position. This part of the trees matches, so we return true. 3. Check if only one node is null.

If one node exists while the other does not, the structures differ. Since the trees are no longer structurally identical, we return false. 4. Compare node values.

If both nodes exist, compare p.val and q.val. If they are different, the trees are not the same, so return false. 5. Recursively compare the left subtrees.

We call the function on p.left and q.left to verify that the left side of both trees matches. 6. Recursively compare the right subtrees.

We call the function on p.right and q.right to verify the right side. 7. Combine the results.

The trees are identical only if both left subtree comparisons and right subtree comparisons return true.

Why it works

The algorithm maintains a simple invariant: at every recursive call, it verifies whether the two subtrees rooted at the current nodes are identical.

If both nodes are absent, they match. If only one exists or their values differ, the invariant is violated and the algorithm returns false. Otherwise, it recursively verifies both child subtrees. Since every node pair is checked exactly once and every structural difference is detected immediately, the algorithm correctly determines whether the trees are identical.

Python Solution

# 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

from typing import Optional

class Solution:
    def isSameTree(
        self,
        p: Optional[TreeNode],
        q: Optional[TreeNode]
    ) -> bool:
        # Both nodes are empty
        if p is None and q is None:
            return True

        # One node exists while the other does not
        if p is None or q is None:
            return False

        # Values do not match
        if p.val != q.val:
            return False

        # Compare left and right subtrees
        return (
            self.isSameTree(p.left, q.left)
            and self.isSameTree(p.right, q.right)
        )

The implementation follows the recursive DFS algorithm directly.

The first condition checks whether both nodes are None. If so, the subtrees match at this position, so we return True.

The second condition handles structural mismatches. If one node exists and the other does not, the trees cannot be identical.

Next, we compare the node values. Even if the structure matches, different values mean the trees are different.

Finally, we recursively compare both left and right subtrees. Since both conditions must be satisfied simultaneously, we use the logical and operator. Python short-circuits evaluation, meaning if the left subtree already fails, the right subtree is not evaluated unnecessarily.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    // Both nodes are nil
    if p == nil && q == nil {
        return true
    }

    // One node exists while the other does not
    if p == nil || q == nil {
        return false
    }

    // Values do not match
    if p.Val != q.Val {
        return false
    }

    // Compare left and right subtrees
    return isSameTree(p.Left, q.Left) &&
        isSameTree(p.Right, q.Right)
}

The Go implementation mirrors the Python logic almost exactly.

The primary difference is the use of nil instead of None. Since Go uses pointers for tree nodes, we compare against nil to determine whether a node exists.

Go also uses && instead of Python's and operator for boolean logic. There are no integer overflow concerns here because node values remain within the int range and no arithmetic is performed.

Worked Examples

Example 1

Input:

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

Tree structure:

    1
   / \
  2   3
Step p Node q Node Comparison Result
1 1 1 Values equal Continue
2 2 2 Values equal Continue
3 null null Both empty True
4 null null Both empty True
5 3 3 Values equal Continue
6 null null Both empty True
7 null null Both empty True

All corresponding nodes match in both structure and value, so the result is:

true

Example 2

Input:

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

Tree structure:

p:       1
        /
       2

q:       1
          \
           2
Step p Node q Node Comparison Result
1 1 1 Values equal Continue
2 2 null Structural mismatch False

At step 2, one subtree exists while the other does not. The algorithm immediately returns:

false

Example 3

Input:

p = [1,2,1]
q = [1,1,2]
Step p Node q Node Comparison Result
1 1 1 Values equal Continue
2 2 1 Value mismatch False

Although the structures match, the values differ at the left child. Therefore:

false

Complexity Analysis

Measure Complexity Explanation
Time O(min(n, m)) to O(n + m) Each corresponding node pair is visited once, with early termination possible
Space O(h) Recursive call stack proportional to tree height

The time complexity is O(n + m) in the worst case, where both trees are identical and every node must be examined. If the trees differ early, the algorithm may terminate sooner.

The space complexity comes from recursion depth. In a balanced tree, the height is O(log n). In the worst case of a skewed tree, recursion depth becomes O(n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1: identical trees
p = TreeNode(1, TreeNode(2), TreeNode(3))
q = TreeNode(1, TreeNode(2), TreeNode(3))
assert solution.isSameTree(p, q) is True  # identical trees

# Example 2: different structure
p = TreeNode(1, TreeNode(2))
q = TreeNode(1, None, TreeNode(2))
assert solution.isSameTree(p, q) is False  # same values, different structure

# Example 3: same structure, different values
p = TreeNode(1, TreeNode(2), TreeNode(1))
q = TreeNode(1, TreeNode(1), TreeNode(2))
assert solution.isSameTree(p, q) is False  # value mismatch

# Both trees empty
assert solution.isSameTree(None, None) is True  # both empty trees

# One tree empty
p = TreeNode(1)
assert solution.isSameTree(p, None) is False  # one empty tree

# Single identical node
p = TreeNode(5)
q = TreeNode(5)
assert solution.isSameTree(p, q) is True  # same single node

# Single different node
p = TreeNode(5)
q = TreeNode(10)
assert solution.isSameTree(p, q) is False  # different root values

# Deep identical tree
p = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3)
)
q = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3)
)
assert solution.isSameTree(p, q) is True  # larger identical tree

# Deep structural mismatch
p = TreeNode(1, TreeNode(2, TreeNode(3)))
q = TreeNode(1, TreeNode(2, None, TreeNode(3)))
assert solution.isSameTree(p, q) is False  # structural mismatch deep in tree
Test Why
[1,2,3] vs [1,2,3] Validates identical trees
[1,2] vs [1,null,2] Verifies structural mismatch detection
[1,2,1] vs [1,1,2] Verifies value mismatch detection
None vs None Confirms two empty trees are equal
Non-empty vs None Tests asymmetric emptiness
Single identical node Smallest non-empty valid input
Single different node Root mismatch handling
Larger identical tree Tests recursion over multiple levels
Deep structural mismatch Ensures mismatches deep in recursion are caught

Edge Cases

Both Trees Are Empty

A common edge case is when both p and q are None. Since neither tree contains any nodes, they are structurally identical and contain the same values by definition. A naive implementation might accidentally return false if it assumes at least one node exists. Our implementation handles this immediately with the condition:

if p is None and q is None:
    return True

One Tree Is Empty

Another important case occurs when one tree exists and the other does not. Even if all observed values match so far, the structures are no longer identical. This could easily introduce bugs if only node values are compared. The implementation explicitly checks for this mismatch and returns False.

Same Values but Different Structure

Two trees can contain exactly the same values while arranged differently. For example:

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

A naive solution that only compares traversed values could incorrectly conclude the trees are equal. Our recursive comparison checks node existence at every position, ensuring structural differences are detected immediately.

Same Structure but Different Values

Even when both trees have identical shapes, corresponding node values must also match. If a single node differs, the trees are not the same. The implementation compares p.val and q.val at every recursive step, guaranteeing value mismatches are caught precisely where they occur.