Same Tree#

Problem#

Given the roots of two binary trees, decide whether they are identical. Two trees are the same when they have the same structure and every corresponding pair of nodes holds the same value.

Example#

Trees 1 -> (2, 3) and 1 -> (2, 3) are the same, so the answer is True. Trees 1 -> (2, null) and 1 -> (null, 2) differ in structure, so the answer is False.

Optimal approach#

Recurse through both trees in lockstep. At each step compare the two current nodes. If both are null, this branch matches, return True. If exactly one is null, or their values differ, the trees diverge here, return False. Otherwise recurse into the left pair and the right pair, and require both to match. The recursion touches each node once.

Solution#

 1class TreeNode:
 2    def __init__(self, val=0, left=None, right=None):
 3        self.val = val
 4        self.left = left
 5        self.right = right
 6
 7
 8def is_same_tree(p: TreeNode | None, q: TreeNode | None) -> bool:
 9    if p is None and q is None:
10        return True
11    if p is None or q is None or p.val != q.val:
12        return False
13    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
14
15
16a = TreeNode(1, TreeNode(2), TreeNode(3))
17b = TreeNode(1, TreeNode(2), TreeNode(3))
18print(is_same_tree(a, b))  # True
19
20c = TreeNode(1, TreeNode(2))
21d = TreeNode(1, None, TreeNode(2))
22print(is_same_tree(c, d))  # False

Complexity#

• Time: O(n), where n is the size of the smaller tree.
• Space: O(h) for the recursion stack.

See the trees topic for related problems, then continue the 60-day challenge.