Same Tree

Given the roots of two binary trees, determine if these trees are identical.

Problem Statement

Two binary trees are identical if they have the same structure and the same values for each pair of corresponding nodes. A node with value

in one tree should have the same value in the other tree for them to be considered identical, regardless of the order of the child nodes.

Rules and Constraints

• The input trees may or may not be empty.
• Each node in the trees should have a non-negative integer key (value).
• No null pointers are given when creating the tree nodes.
• We use the same definition of a binary tree in both trees for comparison.
• Your algorithm should run in O(n) time complexity, where 'n' is the total number of nodes in both trees, and use O(log n) space complexity for recursive function calls if the tree is very unbalanced. If the input trees are balanced, the space complexity should be O(H), where 'H' is the height of the trees.

Note

This problem can be solved iteratively or recursively, but the approach should be efficient to handle trees of different structures and sizes efficiently.

Example

Input: {"p":[1,2,3],"q":[1,2,3]} Output: true