Same Tree

1. The obvious way

   No cheaper way: every node of both trees has to be compared once.

2. The key insight

   Two trees are the same when: both are empty, or both nodes exist with equal values and their left subtrees are the same and their right subtrees are the same. Anything else is different.

3. The algorithm
   1. Both empty? Same.
   2. Only one empty, or values differ? Different.
   3. Otherwise the answer is: left subtrees same AND right subtrees same.

Watch it run

roots equal

def is_same_tree(p, q):
    if p is None and q is None:
        return True                          # both empty: same
    if p is None or q is None or p.val != q.val:
        return False                         # only one empty, or different values
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.