Determine whether two binary trees are structurally identical and contain the same values at every corresponding node.
Given the roots of two binary trees, determine whether the trees are the same.
Two binary trees are considered the same if they have the same structure and every pair of corresponding nodes contains the same value.
Input Format
- Two binary tree roots are provided:
pandq. - Each tree node contains an integer value and references to left and right children.
- A missing child is represented by
null.
In an interview setting, the trees are usually given through node objects or a serialized representation.
Output Format
- Return
trueif the two trees are identical. - Return
falseotherwise.
Constraints
- Compare both structure and node values.
- If one tree has a node where the other has
null, the trees are different. - If both nodes are
nullat the same position, that position matches.
Example 1
Input
p = [1,2,3], q = [1,2,3]
Output
true
Explanation
Both trees have the same shape and the same values at each corresponding node.
Example 2
Input
p = [1,2], q = [1,null,2]
Output
false
Explanation
The trees differ in structure: the left tree has a left child of 2, while the right tree has a right child of 2.
Show 1 more example
Example 3
Input
p = [1,2,1], q = [1,1,2]
Output
false
Explanation
The root values match, but the left and right subtrees do not match in value.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.