Identical Binary Trees

EASY10 pts

You are given the root nodes of two binary trees, tree1 and tree2. Your task is to determine whether these two trees are identical.

Two binary trees are considered identical if and only if:

They have the exact same structure (i.e., the arrangement of nodes is identical), and
Every corresponding node in both trees contains the same value.

In other words, if you were to overlay one tree on top of the other, every node should perfectly align in both position and value.

Return true if the two binary trees are identical, and false otherwise.

Example

Input

tree1 = [1,2,3]
tree2 = [1,2,3]

Output

true

Explanation

Both trees have identical structure with the same root value 1, left child 2, and right child 3. Every node matches in position and value, making the trees identical.

Example

Input

tree1 = [1,2]
tree2 = [1,null,2]

Output

false

Explanation

In tree1, node 2 is the left child of root 1. In tree2, node 2 is the right child of root 1. Although both trees contain the same values {1, 2}, their structures differ, so they are not identical.

Example

Input

tree1 = [1,2,1]
tree2 = [1,1,2]

Output

false

Explanation

Both trees have the same structure (root with two children), but the values of corresponding nodes differ. tree1 has left child 2 and right child 1, while tree2 has left child 1 and right child 2. The trees are not identical.

Accepted0/0·0% Acceptance

Constraints

The number of nodes in each tree is in the range [0, 100].
-10⁴ ≤ Node.val ≤ 10⁴
Both trees may be empty (null roots), in which case they are considered identical.

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

p =

[1,2,3]

q =

[1,2,3]

Loading problem...

Identical Binary Trees

Hints

Identical Binary Trees

Hints