IQ Lab: coding interviews from the first loop

easyTrees, depth-firstRecursion target 15 min

Same tree

You get the roots p and q of two binary trees. Return True if they are the same tree and False if not. Two trees are the same when they have the same shape and every pair of nodes in matching positions holds equal values. Two empty trees (None and None) are the same.

Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing.

Example 1

Inputp = [5, 3, 8, 1], q = [5, 3, 8, 1]OutputTrue

Same shape, same value in every position.

Example 2

Inputp = [5, 3], q = [5, None, 3]OutputFalse

Same values, different shape: 3 is a left child in p and a right child in q.

Example 3

Inputp = [5, 3, 8], q = [5, 8, 3]OutputFalse

Same shape, but the two children hold different values.

Constraints

0 ≤ number of nodes in each tree ≤ 100
-10⁴ ≤ node values ≤ 10⁴

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern