Introduction

Same Tree means:

  • checking whether
  • two binary trees
  • are completely identical

Conditions:

  • structure must match
  • node values must match

Example:

Tree 1:
        1
      /   \
     2     3

Tree 2:
        1
      /   \
     2     3

Output:
True

Explanation:

Both trees have:
- same structure
- same node values

This problem is one of the most important applications of:

DFS Traversal

Constraints

1 <= Number of Nodes <= 10^5

Approach : Recursive DFS Solution

Explanations:

Explanation:

The idea is:

  • recursively compare nodes
  • in both trees simultaneously

Steps:

  1. Compare current nodes.
  2. Check node values.
  3. Recurse left subtree.
  4. Recurse right subtree.

Conditions:

  • both nodes null → valid
  • one node null → invalid
  • values mismatch → invalid

This approach:

  • uses DFS recursion
  • compares tree structure and values

Dry Run

Compare:
1 and 1
Values match.

Compare left:
2 and 2
Values match.

Compare right:
3 and 3
Values match.

All nodes matched.
Trees are identical.

Practice :

Complexity Analysis :

Time Complexity:- O(n)
Explanation :
Every tree node is compared once.

Space Complexity:- O(h)
Explanation :
Recursion stack depends on tree height.

Why This Problem is Important

This problem builds the foundation for:

  • DFS traversal
  • Tree recursion
  • Tree comparison
  • Recursive validation
  • Binary tree processing

Real-World Applications

Same tree concepts are used in:

  • File system comparison
  • Syntax tree validation
  • XML/JSON comparison
  • Version control systems
  • Structural verification

Common Beginner Mistakes

  • Forgetting null checks
  • Incorrect recursion flow
  • Wrong comparison order
  • Missing value validation
  • Returning incorrect boolean values

Interview Tip

Interviewers often expect:

  • DFS understanding
  • recursion explanation
  • tree comparison logic
  • recursive validation clarity

Always explain:

  • node comparison logic
  • subtree recursion
  • null handling conditions

Related Questions

  • Path Sum
  • Symmetric Tree
  • Tree Height
  • DFS Traversal
  • Balanced Binary Tree

Final Takeaway

The Same Tree problem is one of the most important beginner DFS tree problems.

It teaches:

  • DFS recursion
  • recursive comparison
  • tree traversal
  • structural validation

Understanding this problem builds a strong foundation for:

  • advanced tree problems
  • graph traversal
  • interview-level algorithms.