""" Same Tree Given two binary trees, check if they are structurally identical and the nodes have the same values. Reference: https://en.wikipedia.org/wiki/Binary_tree Complexity: Time: O(min(n, m)) where n and m are sizes of the trees Space: O(min(h1, h2)) where h1 and h2 are the heights """ from __future__ import annotations from algorithms.tree.tree import TreeNode def is_same_tree(tree_p: TreeNode | None, tree_q: TreeNode | None) -> bool: """Check whether two binary trees are identical. Args: tree_p: The root of the first binary tree. tree_q: The root of the second binary tree. Returns: True if both trees are structurally identical with equal node values, False otherwise. Examples: >>> is_same_tree(None, None) True """ if tree_p is None and tree_q is None: return True if tree_p is not None and tree_q is not None and tree_p.val == tree_q.val: return is_same_tree(tree_p.left, tree_q.left) and is_same_tree( tree_p.right, tree_q.right ) return False