Big O Practice: Same Tree

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

Variables

• n - number of nodes in either tree
• h - height of the trees

Explanation

In the worst case (trees identical) every node is visited - **O(n)** time. Recursion stack uses **O(h)** space; balanced is `log n`, skewed is `n`. Early exit on mismatch only improves the constant, not the asymptotic.

More Big O practice problems · Today's daily problem