FresherFresher (0–1 yrs)CodingPythonAmazonBloomberg

Same Tree

Check whether two binary trees are structurally identical and have the same node values.

Answers use simple, clear English.

Time: O(n)Space: O(h)

Quick interview answer

DFS both in lockstep: if both null → true; if one null or values differ → false; else compare left/left and right/right.

Detailed answer

DFS both in lockstep: if both null → true; if one null or values differ → false; else compare left/left and right/right. Can also serialize both and compare strings, but lockstep DFS is clearer.

Full explanation

Can also serialize both and compare strings, but lockstep DFS is clearer.

Real example & use case

Regression test asserting two DOM-diff ASTs match after a refactor.

Pros & cons

Pros: O(n) short code. Cons: recursion depth on deep trees.

Code example

def is_same_tree(p, q) -> bool:
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

Practice code · python (view only · no execution)

def is_same_tree(p, q) -> bool:
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

#tree#dfs