Skip to main content
DSA patterns

Same Tree

easyTrees Must-doAmazonAccentureCognizant

Problem statement

You are given the roots of two binary trees, p and q. Return true if the two trees are the same — meaning they have exactly the same shape (the same nodes present in the same left/right positions) and every corresponding pair of nodes holds the same value. Return false otherwise.

This is the same question you'd ask when comparing two versions of a config tree, two parsed ASTs, or two directory structures for drift: not just "do they contain the same values somewhere", but "is every node in exactly the same place with exactly the same value."

Examples

Example 1

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

Output: true

Explanation: both trees have root 1 with left child 2 and right child 3 — identical shape and identical values at every position.

Example 1

Example 2

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

Output: false

Explanation: in p, the 2 is a left child; in q, the 2 is a right child. Same values overall, but different shapes, so the trees are not the same.

Example 2

Example 3

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

Output: false

Explanation: both trees have the same shape (a root with two children), but the left and right values are swapped — p's left child is 2 and right child is 1, while q's are the other way around.

Example 3

Hints

Hint 1: Two trees can only be the same if their roots match and their left subtrees match each other and their right subtrees match each other — this is a definition you can apply again to each pair of subtrees.

Approach

Optimal: Iterative BFS

Intuition

Instead of recursing down and combining results on the way back, walk both trees in lockstep using a queue of pairs: at every step, take one pair (node from p, node from q) off the queue and compare them directly. If they match, queue up their two children as new pairs — (p.left, q.left) and (p.right, q.right) — and keep going. The moment any pair fails to match (different values, or one side missing where the other isn't), the whole check can return false right away, without processing whatever else is still sitting in the queue.

Steps

  1. Put the pair (p, q) — the two roots — into a queue.
  2. While the queue isn't empty, remove the next pair.
  3. If both nodes in the pair are null, this pair matches — move on to the next pair in the queue.
  4. If exactly one of the two is null, the trees differ in shape here — return false immediately.
  5. If both exist but their values differ, return false immediately.
  6. Otherwise, queue up the pair of left children and the pair of right children, and continue.
  7. If the queue empties without ever returning false, every pair matched — return true.

Dry run

p = [1,2], q = [1,null,2] (Example 2): p has root 1 with a left child 2 and no right child; q has root 1 with no left child and a right child 2.

step pair dequeued check action
1 (1, 1) both non-null, values equal queue (2, null) and (null, 2)
2 (2, null) one is null, the other isn't return false

Result: false, matching Example 2 — the mismatch is caught as soon as the left-child pair is dequeued, without ever looking at the right-child pair still waiting in the queue.

Edge cases: if both roots are null, the very first pair dequeued is (null, null), which is treated as a match, and the queue is then empty — the loop ends and returns true.

Complexity

Time O(n) - where n is the number of nodes in the smaller tree. Each pair of corresponding nodes is enqueued and dequeued exactly once, and the work per pair (comparing values and queueing the next pair of children) is O(1).

Space O(w) - where w is the maximum width of either tree at any level. The queue holds pairs of nodes level by level, so its size tracks how wide the trees get, not how deep — the opposite trade-off from the recursive version's stack.

from collections import deque
from typing import Optional


# 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:
        queue = deque([(p, q)])
        while queue:
            node1, node2 = queue.popleft()
            if node1 is None and node2 is None:
                continue
            if node1 is None or node2 is None:
                return False
            if node1.val != node2.val:
                return False
            queue.append((node1.left, node2.left))
            queue.append((node1.right, node2.right))
        return True


def build_tree(values: list) -> Optional[TreeNode]:
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values):
            if values[i] is not None:
                node.left = TreeNode(values[i])
                queue.append(node.left)
            i += 1
        if i < len(values):
            if values[i] is not None:
                node.right = TreeNode(values[i])
                queue.append(node.right)
            i += 1
    return root


if __name__ == "__main__":
    def fmt(b: bool) -> str:
        return "true" if b else "false"

    p1, q1 = build_tree([1, 2, 3]), build_tree([1, 2, 3])
    p2, q2 = build_tree([1, 2]), build_tree([1, None, 2])
    p3, q3 = build_tree([1, 2, 1]), build_tree([1, 1, 2])

    print(fmt(Solution().isSameTree(p1, q1)))
    print(fmt(Solution().isSameTree(p2, q2)))
    print(fmt(Solution().isSameTree(p3, q3)))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "check if two trees are the same" — compares both shape and values at every corresponding position, not just contents
  • Idea: recursively check (both null) or (both non-null, same value, same left subtree, same right subtree); fail fast on the first mismatch
  • Cost: O(n) time either way; O(h) space for recursive DFS (call stack), O(w) space for iterative BFS (widest level)
  • Trap: treating "same values present" as equivalent to "same tree" — position and shape matter just as much as the values themselves
  • Remember: isSameTree is the building block for Subtree of Another Tree and (with left/right swapped on one side) Symmetric Tree

Interview follow-ups

  • Instead of true/false, return the first path (list of values) where the two trees diverge.

    Thread a running path (say, a list of values from the root down to the current node) through the recursion, and the moment a mismatch is found — differing values, or one side null and the other not — return that accumulated path instead of just false. Every other case still recurses and appends the current node's value before descending. This keeps the same O(n) time bound in the worst case, with O(h) extra space for the path itself, and turns a bare yes/no answer into something a human can act on immediately.

  • The trees are enormous and stored on different machines — comparing every node would be far too much network traffic.

    Instead of walking both trees, compute a content-based hash of each subtree (e.g., combine a node's own value with the hashes of its left and right subtrees) and compare only the two root hashes first. If the root hashes differ, the trees definitely differ, and you can then recursively descend and compare hashes level by level to find where they diverge, only pulling the actual node data across the network for the specific branch that doesn't match. This turns "compare everything" into "fetch just enough to localize the difference."

  • What if node values can repeat, and structural equality (ignoring values entirely) is all that matters?

    Drop the value comparison from the equality check entirely: two nodes now "match" as long as they agree on which of their two children exist (both present, both absent, or the same one present on both sides), and the recursion into left and right subtrees proceeds exactly as before. The time and space complexity are unchanged, since the value check was already O(1) — removing it just changes what counts as a match, not how much work is done.

Frequently asked questions

Checking the current pair's null-ness and values first means a mismatch is caught at the shallowest possible point, before any deeper (and pointless) recursive calls are made. If the roots already have different values, there is no reason to ever compare their subtrees — the answer is already false. This short-circuiting is what keeps the approach at O(n) instead of doing extra unnecessary work.

No — that would be a much weaker check. p = [1,2,3] and a tree shaped like [1,3,2] contain the same three values, but they are not the "same tree" under this problem's definition, since the values sit in swapped positions. This problem cares about structure and position together, not just which values appear somewhere in the tree.

Subtree of Another Tree reuses isSameTree directly: it walks one tree looking for any node where isSameTree(that node, the other tree's root) returns true. Symmetric Tree is a variant of this same comparison, but instead of comparing a tree to a second, separate tree, it compares a tree's left subtree to its own right subtree, with left and right swapped at every step (checking p.left against q.right and p.right against q.left) to test for mirror symmetry.

Yes — GeeksforGeeks describes an O(1)-extra-space approach using Morris traversal, which temporarily rewires null right-pointers into "threads" back to an ancestor to simulate the call stack without actually using one, then removes the threads afterward. It reaches the same O(n) time bound with O(1) auxiliary space instead of O(h) or O(w), but the bookkeeping is intricate enough that it's rarely worth reaching for outside of a strict memory-constrained setting.

Comparing two tree-shaped structures for exact equality is a common building block: diffing two versions of a parsed config, verifying that a deployed resource tree matches its declared spec, or checking that two ASTs produced by different runs of a parser agree. The core lesson here — define equality recursively in terms of the roots and their subtrees, and fail fast on the first mismatch — applies directly to any of those comparisons.