A-050● Day 502026.06.25easyleetcode #100neetcode150

Same Tree

#tree#depth-first-search#breadth-first-search#binary-tree

Problem

· problem

P.050

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.

constraints

· The number of nodes in both trees is in the range [0, 100]
· -10⁴ ≤ Node.val ≤ 10⁴

// paraphrased summary — see source for full text

examples

example 1input → output

[1,2,3]
[1,2,3]

true

example 2input → output

[1,2]
[1,null,2]

false

example 3input → output

[1,2,1]
[1,1,2]

false

Pre-solve

· pre-solve

● 1list shown→● 2select→● 3reveal

☐
If both trees are empty, should we return true?
☐
What if one tree is empty and the other has nodes?
☐
If node values are the same but left and right children are swapped, are they the same tree?
☐
Can we solve this using an iterative approach?
☐
Can we serialize both trees to strings and compare them?
☐
Is comparing inorder traversals sufficient?

check the items you would ask, then press confirm

// session-only state — refresh resets (repeatable practice)

Logic Structure

· logic

● 1slots shown→● 2pick per slot→● 3reveal

// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.

step 1· Base case: both nodes are null

○

if not p and not q:

○

if not p or not q:

○

if p is None and q is None:

step 2· Return true for base case│ nested

○

return True

○

return False

○

continue

step 3· Recursive condition: both nodes exist and have equal values

○

if p and q and p.val == q.val:

○

if p or q and p.val == q.val:

○

if p and q and p.val != q.val:

○

if p and q:

step 4· Recursive call: compare left and right subtrees│ nested

○

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

○

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

○

return self.isSameTree(p.left, q.left) or self.isSameTree(p.right, q.right)

○

return self.isSameTree(p, q)

step 5· Mismatch case: return false

○

else:

○

else: return True

○

else: return self.isSameTree(p.right, q.right)

pick one option per slot

// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.

Solve · Trace

· solve

solution.py

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

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

mental dry-run cases

// walk each case in your head; expand the worked example below if stuck.

case 1

[1,2,3]
[1,2,3]

→

true

case 2

[1,2]
[1,null,2]

→

false

case 3

[1,2,1]
[1,1,2]

→

false

// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.