LeetCode 100: Same Tree Solution in Python Explained

Problem Statement

In LeetCode 100, you’re given the roots of two binary trees, p and q. Your task is to return true if they are identical—same structure and node values—or false if they differ. This contrasts with BST recovery like LeetCode 99: Recover Binary Search Tree, focusing on equality rather than correction.

Constraints

• Number of nodes in each tree: 0 <= n <= 100
• Node values: -10^4 <= Node.val <= 10^4

Example

Let’s see some cases:

Copy codeInput: p = [1,2,3], q = [1,2,3]
     p:   1       q:   1
         / \          / \
        2   3        2   3
Output: true
Explanation: Identical structure and values.

Copy codeInput: p = [1,2], q = [1,null,2]
     p:   1       q:   1
         /            \
        2              2
Output: false
Explanation: Different structures (left vs. right child).

Copy codeInput: p = [1,2,1], q = [1,1,2]
     p:   1       q:   1
         / \          / \
        2   1        1   2
Output: false
Explanation: Same structure, different values.

These examples show we’re checking for exact tree equality.

Understanding the Problem

How do you solve LeetCode 100: Same Tree in Python? Take p = [1,2,3], q = [1,2,3]. We need to confirm they’re identical—both have root 1, left 2, right 3, true. For p = [1,2], q = [1,null,2], structures differ (left vs. right), false. This isn’t a BST validation like LeetCode 98: Validate Binary Search Tree; it’s about tree comparison. We’ll use: 1. Recursive Comparison: O(n) time, O(h) space—our best solution. 2. Stack-Based Comparison: O(n) time, O(h) space—an alternative.

Let’s dive into the primary solution.

Solution 1: Recursive Comparison Approach (Primary)

Explanation

Recursive Comparison checks tree equality by recursively comparing corresponding nodes—roots, left subtrees, and right subtrees. If both are null, they’re equal; if one is null or values differ, they’re not. It’s the best solution due to its simplicity, directness, and alignment with tree structure, making it efficient and intuitive.

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

• Root: 1 = 1.
• Left: 2 = 2.
• Right: 3 = 3.
• All match, true.

Step-by-Step Example

Assume a TreeNode class: class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right.

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

Goal: Return true.

• Start: Call isSameTree(p=1, q=1).
• Step 1: p = 1, q = 1.
• Not null, 1 = 1, true.
• Left: isSameTree(p.left=2, q.left=2).
• 2 = 2, no children, true.
• Right: isSameTree(p.right=3, q.right=3).
• 3 = 3, no children, true.
• Finish: Return true.

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

Goal: Return false.

• Start: isSameTree(p=1, q=1).
• Step 1: p = 1, q = 1.
• 1 = 1, true.
• Left: isSameTree(p.left=2, q.left=None).
• 2 ≠ None, false, stop.
• Finish: Return false.

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

Goal: Return false.

• Start: isSameTree(p=1, q=1).
• Step 1: p = 1, q = 1.
• 1 = 1, true.
• Left: isSameTree(p.left=2, q.left=1).
• 2 ≠ 1, false, stop.
• Finish: Return false.

How the Code Works (Recursive Comparison) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    # Line 1: Check if both nodes are null
    if not p and not q:
        # If p and q are None (e.g., leaves’ children), identical
        return True

    # Line 2: Check if one node is null
    if not p or not q:
        # If one is None and other isn’t (e.g., p=2, q=None), different
        return False

    # Line 3: Compare current node values
    if p.val != q.val:
        # If values differ (e.g., p.val=2, q.val=1), not same
        return False

    # Line 4: Recursively compare left subtrees
    left_same = isSameTree(p.left, q.left)
    # Checks left children (e.g., p.left=2, q.left=2)
    # Returns true if subtrees match

    # Line 5: Recursively compare right subtrees
    right_same = isSameTree(p.right, q.right)
    # Checks right children (e.g., p.right=3, q.right=3)
    # Returns true if subtrees match

    # Line 6: Return combined result
    return left_same and right_same
    # True only if both subtrees are identical (e.g., true for [1,2,3])
    # Ensures full tree equality

This detailed breakdown clarifies how recursive comparison efficiently verifies tree equality.

Alternative: Stack-Based Comparison Approach

Explanation

Stack-Based Comparison uses a stack to traverse both trees simultaneously, comparing nodes level-by-level. Push root pairs, pop and check values, then push children. It’s a practical alternative, avoiding recursion while maintaining clarity.

For [1,2,3] vs. [1,2,3]:

• Stack: [(1,1)], pop, match, push (2,2), (3,3).
• All match, true.

Step-by-Step Example (Alternative)

For [1,2,3] vs. [1,2,3]:

• Start: stack = [(1,1)].
• Step 1: Pop (1,1), 1 = 1, push (2,2), (3,3).
• Step 2: Pop (2,2), 2 = 2, no children.
• Step 3: Pop (3,3), 3 = 3, no children.
• Finish: Return true.

For [1,2] vs. [1,null,2]:

• Step 1: Pop (1,1), push (2,None), (None,2).
• Step 2: Pop (2,None), mismatch, false.
• Finish: Return false.

How the Code Works (Stack-Based)

Copy codedef isSameTreeStack(p: TreeNode, q: TreeNode) -> bool:
    stack = [(p, q)]
    while stack:
        node1, node2 = stack.pop()
        if not node1 and not node2:
            continue
        if not node1 or not node2 or node1.val != node2.val:
            return False
        stack.append((node1.left, node2.left))
        stack.append((node1.right, node2.right))
    return True

Complexity

• Recursive Comparison:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.
• Stack-Based Comparison:
• Time: O(n) – visits each node once.
• Space: O(w) – stack size, w = max width.

Efficiency Notes

Recursive Comparison is the best solution with O(n) time and O(h) space, offering a clean, intuitive approach—Stack-Based Comparison matches time complexity with O(w) space, providing a robust alternative when recursion is a concern.

Key Insights

• Node-by-Node: Compare structure and value.
• Base Cases: Handle null nodes.
• Traversal: Ensures full equality.

Additional Example

For p = [1,2,3,4], q = [1,2,3,4]:

• Goal: true.
• Recursive: All nodes match → true.

Edge Cases

• Empty Trees: [], [] → true.
• Single Node: [1], [1] → true.
• Different Values: [1,2], [1,3] → false.

Both solutions handle these well.

Final Thoughts

LeetCode 100: Same Tree in Python is a great tree comparison challenge. The Recursive Comparison solution excels with its simplicity and efficiency, while Stack-Based Comparison offers a non-recursive option. Want more? Try LeetCode 94: Binary Tree Inorder Traversal for traversal or LeetCode 98: Validate Binary Search Tree for BST validation. Ready to practice? Solve LeetCode 100 on LeetCode with [1,2,3] and [1,2,3], aiming for true—test your skills now!