Framework Thinking - Neetcode 150 - Same Binary Tree

Here is solutions for Same Binary Tree.

1. Understand the problem

You are given two binary trees, p and q.
A tree is the same as another tree if:
- They have the same structure.
- Each node at corresponding positions has the same value.

You must return True if the trees are identical, otherwise False.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

Can the input trees be empty (None)?

Yes. Two empty trees → return True. One empty, one not → False.

Can node values be negative or duplicated?

Yes, any integer. Duplicates possible, so structure matters.

What is the maximum number of nodes?

Typically up to 10⁴ nodes. A recursive DFS is safe unless tree is extremely skewed.

Does time complexity matter?

Yes, aim for O(n). You must compare each node at most once.

Do we need to modify the trees?

No, only read/access nodes.

3. Explore examples.

Example 1: Same trees

p:        1         q:        1
         / \                 / \
        2   3               2   3

Output: True

Different structures

p:        1         q:        1
         /                   / \
        2                   2   3

Output: False

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1 — Recursive DFS - Time O(N), Space O(H)

Key idea:

A tree is same only if:
Both nodes are None → True
Idea: Return True/False.

same(p, q) = (p.val == q.val)
             AND same(p.left, q.left)
             AND same(p.right, q.right)

Time: O(N)
Space: O(H)

4.2. Iterative BFS in 2 trees - Time O(N), Space O(N / 2)

Key idea:

- Use a queue of node pairs (p, q)

At each step:

- If both None → continue

- If one None → False

- If values differ → False

- Push children pairs (p.left, q.left) and (p.right, q.right)

Time: O(N)
Space: O(N / 2)

4.3. Iterative DFS using Stack in 2 trees - Time O(N), Space O(H), worst case O(N)

Key idea:
- Same idea but using stack.
Time: O(N)
Space: O(N)

5. Implement solutions.

5.1. DFS Recursion - Time O(N), Space O(N)

# 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

Time: O(N).
Space: O(H).
- Best case (balanced tree): O(logN)
- Worst case (skewed tree): O(N)

5.2. Iterative DFS - Time O(N), Space O(H), worst case O(N)

# 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:
        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.right, node2.right))
            stack.append((node1.left, node2.left))

        return True

Time: O(N).
Space: O(N).

5.3. Iterative BFS - Two Queues - Time O(N), Space O(N / 2)

# 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:
        q1 = deque([p])
        q2 = deque([q])

        while q1 and q2:
            for _ in range(len(q1)):
                nodeP = q1.popleft()
                nodeQ = q2.popleft()

                if nodeP is None and nodeQ is None:
                    continue
                if nodeP is None or nodeQ is None or nodeP.val != nodeQ.val:
                    return False

                q1.append(nodeP.left)
                q1.append(nodeP.right)
                q2.append(nodeQ.left)
                q2.append(nodeQ.right)

        return True

Time: O(N)
Space: O(N / 2)

6. Dry run testcases.

Testcase:

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

p node	q node	Condition	Result
1	1	equal → check children	continue
2	2	equal → check children	continue
None	None	both None	True
None	None	both None	True
3	3	equal → check children	continue
None	None	both None	True
None	None	both None	True

December 2, 2025