Same Tree Checker

Given two binary trees, determine if they are structurally identical and have the same node values. This is a fundamental problem in tree data structures, essential for tasks like comparing configurations, validating data structures, or detecting duplicates.

Problem Description

You are given the roots of two binary trees, tree1 and tree2. Your task is to write a function that returns true if both trees are the same, and false otherwise.

Two binary trees are considered the same if they are structurally identical, meaning they have the same shape, and the corresponding nodes have the same value.

Key Requirements:

• Compare the structure of both trees.
• Compare the values of corresponding nodes.
• Handle cases where one or both trees might be empty.

Expected Behavior:

• If both trees are identical, return true.
• If the trees differ in structure or node values, return false.

Edge Cases to Consider:

• Both trees are empty (null).
• One tree is empty, and the other is not.
• Trees with only a root node.
• Trees with different structures but same node values.
• Trees with the same structure but different node values.

Examples

Example 1:

Input:
tree1:
    1
   / \
  2   3

tree2:
    1
   / \
  2   3

Output: true
Explanation: Both trees have the same structure and node values.

Example 2:

Input:
tree1:
    1
   /

tree2:
    1
     \

Output: false
Explanation: The trees have different structures.

Example 3:

Input:
tree1:
    1
   / \
  2   1

tree2:
    1
   / \
  1   2

Output: false
Explanation: The trees have the same structure but different node values at the left and right children.

Example 4:

Input:
tree1: null
tree2: null

Output: true
Explanation: Both trees are empty and therefore considered the same.

Example 5:

Input:
tree1:
    1

tree2: null

Output: false
Explanation: One tree is empty, and the other is not.

Constraints

• The number of nodes in each tree will be between 0 and 100, inclusive.
• Node values will be integers within a standard integer range.
• The tree nodes are represented by a structure/class with a value field and left and right child pointers.

Notes

• A recursive approach is often natural for solving tree problems. Consider what the base cases for your recursion would be.
• Think about the conditions under which two nodes, and their entire subtrees, can be considered identical.
• The problem is language-agnostic, but you will likely need to define a basic TreeNode structure for conceptualizing your solution.