Check if Two Trees are Identical

To solve this efficiently, I would use a Depth-First Search approach with recursion. First, I need to establish clear base cases. If both input roots are null, the trees are identical up to this point, so I return true. However, if only one of them is null while the other exists, the structures differ, so I return false immediately. Next, I check if the values of the current nodes match. If they do not, the trees are not identical, and I return false. If the values match, I must ensure the entire subtree structure is the same. I do this by recursively calling the function on the left children and the right children of both trees. The result is true only if both recursive calls return true. For example, consider two trees where the root is 1, left child is 2, and right child is 3. If the second tree has the same structure and values, my function compares roots, then recurses to compare left nodes (2 vs 2), then right nodes (3 vs 3). Since all checks pass, it returns true. This approach ensures we visit every node exactly once, giving us O(n) time complexity. Regarding space, the recursion stack goes as deep as the height of the tree, resulting in O(h) space complexity, which is optimal for this problem.