Check if two trees are identical or not

Problem Overview

In this article, we will discuss the LeetCode problem titled "Same Tree". This problem falls under the category of Binary Trees, which is a vital topic in data structures and algorithms. LeetCode problem statements often challenge our understanding of fundamental concepts in binary trees and recursion.

The problem is accessible on LeetCode - Same Tree.

Problem Statement

You are given two binary trees and you need to determine if they are the same. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Understanding the Problem

To solve this problem, you are provided with the roots of two binary trees. The aim is to check whether these two trees are the same. Let's break down what 'same' means in this context:

1. Structure Match: Both trees must have the same structure, i.e., the arrangement of nodes should be identical at every level.
2. Value Match: Corresponding nodes in both trees should have the same value.

A good approach to understanding and solving this problem is leveraging depth-first traversal methods to iterate over both trees simultaneously and compare each node and its structure.

Key DSA Concepts and Theory

Understanding this problem requires familiarity with binary trees, recursion, and depth-first search (DFS).

1. Binary Tree

A binary tree is a hierarchical data structure in which each node has at most two children referred to as the left child and right child.

2. Recursion

Recursion involves solving a complex problem by breaking it down into simpler sub-problems of the same type. It is commonly used in problems involving tree structures due to their naturally recursive nature.

3. Depth-First Search (DFS)

DFS is an algorithm for traversing or searching tree or graph data structures. We can use DFS to explore as far as possible along a branch before backtracking. A recursive approach to DFS suits this problem well.

Solution Approach

To determine whether two trees are the same, we can use a recursive approach. Here’s a step-by-step strategy with both C++ and Java code examples.

Steps:

1. Base Case:

   • If both nodes are null, they are inherently the same at this point in the structure of the tree.
   • If one of the nodes is null and the other is not, the trees are not the same.
   • If the values of the nodes differ, the trees are not the same.

2. Recursive Case:

   • Recursively check the left subtree and the right subtree to ensure that both the structure and node values are identical.

C++ Code Implementation

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // Base case
        if (p == nullptr && q == nullptr) return true;
        if (p == nullptr || q == nullptr) return false;
        if (p->val != q->val) return false;

        // Recursive case for left and right subtree
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

Java Code Implementation

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // Base case
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        
        // Recursive case for left and right subtree
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Time and Space Complexity Analysis

Time Complexity

The time complexity of the solution is O(N), where N is the number of nodes in the binary trees. This is because, in the worst case, we may need to compare all nodes of both trees.

Space Complexity

The space complexity is O(H), where H is the height of the tree. This space is used for the recursion stack. In the worst case, the tree could have a structure that could lead to a space complexity of O(N) if it resembles a linked list in depth.

Common Mistakes to Avoid

• Ignoring Null Checks: Ensure that both trees are checked for null nodes since forgetting this can lead to runtime errors.
• Incorrect Recursive Logic: Mistakenly comparing mismatched nodes or using incorrect logic in recursion can lead to inaccurate results.

Similar Problems on LeetCode

1. 1008. Construct Binary Search Tree from Preorder Traversal
2. 572. Subtree of Another Tree
3. 101. Symmetric Tree
4. 226. Invert Binary Tree

Additional Resources and References

• Binary Tree - Detailed Explanation on Wikipedia
• Understanding Recursion and its Application

This article has covered the concepts and solution for the "Same Tree" problem on LeetCode comprehensively, and I hope it helps you in understanding the necessary steps to tackle similar problems effectively.