Same Tree (LeetCode #100)

Challenge Statement

• Given the roots of two binary trees p and q, write a function to check if they are the same or not.
• Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
• This challenge corresponds to LeetCode #100.

Constraints

• The number of nodes in both trees is in the range [0, 100].
• -104 <= Node.val <= 104

Example 1:

Input: p = [1, 2, 3], q = [1, 2, 3]
Output: true

Example 2:

Input: p = [1,2], q = [1, null, 2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1, 1, 2]
Output: false

Solution

Below is my solution and some test cases. This solution has a linear time complexity O(p + q) and a linear space complexity O(p + q), where p and q are the sizes of the input trees.