Same Tree Check

Determine if two binary trees are structurally identical and have the same values.

binary tree recursion tree traversal

Given two binary trees, determine if they are the same tree. Two binary trees are considered the same if they are structurally identical and the nodes have the same values.

Define a class `TreeNode` with attributes `val`, `left`, and `right`. The constructor is `__init__(self, val=0, left=None, right=None)`.

Implement a function `is_same_tree(p: TreeNode | None, q: TreeNode | None) -> bool` that returns `True` if the trees rooted at `p` and `q` are the same, and `False` otherwise.

You may assume all node values are integers.

Constraints

The number of nodes in each tree is in the range [0, 100]. Node values are integers in the range [-10^4, 10^4]. Your solution should run in O(n) time and use O(h) recursion stack space, where n is the number of nodes and h is the height of the tree.

Example

>>> # Tree1:   1          Tree2:   1
>>> #          / \                 / \
>>> #         2   3               2   3
>>> p = TreeNode(1, TreeNode(2), TreeNode(3))
>>> q = TreeNode(1, TreeNode(2), TreeNode(3))
>>> is_same_tree(p, q)
True

>>> # Tree1:   1          Tree2:   1
>>> #          /                   \
>>> #         2                     2
>>> p = TreeNode(1, TreeNode(2))
>>> q = TreeNode(1, None, TreeNode(2))
>>> is_same_tree(p, q)
False

>>> is_same_tree(None, None)
True

>>> is_same_tree(None, TreeNode(1))
False

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

If both nodes are None, they are equal. If only one is None, they are not equal.

Compare the values of the current nodes, then recursively check left and right subtrees.

The recursion must check that both left subtrees are the same AND both right subtrees are the same.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.