100. Same Tree

[#binary-tree, #dfs]

## description

## 100. Same Tree

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 1:

plain text

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

Example 2:

plain text

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

Example 3:

plain text

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

–
The number of nodes in both trees is in the range [0, 100].
–
-104 <= Node.val <= 104

Constraints:

## notes

### Intuition

Two trees are identical if their structure and node values match exactly. By traversing both trees simultaneously, we can compare nodes at each position.

### Implementation

Use recursive DFS to check both trees in parallel. The base case is when both p and q are null—this means we've reached the end of both subtrees successfully, so return true. If both nodes exist and their values match, recursively verify that the left subtrees are the same AND the right subtrees are the same. If any of these conditions fail, return false.

### Edge-cases

No special edge cases beyond the base conditions. The recursion naturally handles trees of different shapes or sizes since a mismatch (one null, one not) will return false.

–
Time: O(n) — visit each node once
–
Space: O(h) — recursion stack depth equals tree height

### Complexity

## solution

python

from typing import Optional
from lcutils import TreeNode

# 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: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if p and q and p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()

--EOF--