Check if two trees are identical or not

Binary Trees Medium Problems Medium

Fun Fact: The given problem is fundamentally used in various applications such as code compilers and database systems where we need to compare two Abstract Syntax Trees (ASTs)
It's also used in code similarity checkers and plagiarism detection software where they need to analyze if two codes perform the same operations
In Data Science and ML applications, this concept is helpful in measuring the similarities between decision trees

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

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

Examples:

Input : p = [1, 2, 3] , q = [1, 2, 3]

Output : true

Explanation : Both trees images are shown below

Input : p = [1, 2, 1] , q = [1, 1, 2]

Output : false

Explanation : Both trees images are shown below

Input : p = [5, 1, 2, 8, null, null, 5, null, 4, null, null, 7 ], q = [5, 1, 2, 8, null, null, 4, null, 5, null, null, 7 ]

Constraints

1 <= Number of Nodes <= 100
-10⁴ <= Node.val <= 10⁴

Hints

An iterative DFS approach can be implemented using a stack to simulate recursion. Each time we pop a node pair (p, q), we compare their values and push their left and right children back onto the stack for further comparison.

Company Tags

Teladoc Health Deloitte Wayfair Siemens Healthineers Broadcom Optum PayPal Chewy Rakuten McKinsey & Company Activision Blizzard Rockstar Games Snowflake Western Digital AMD Swiggy Epic Games Etsy Target Electronic Arts DoorDash NVIDIA Boston Consulting Group Robinhood Riot Games Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

Intuition

To determine whether two binary trees are identical, one effective method is to traverse both trees simultaneously, comparing the values and structure of corresponding nodes at each step. The key idea is that two trees are identical if and only if every corresponding pair of nodes in the two trees have the same value and the same left and right subtrees. This requires ensuring that not only the values match, but that the structure of the trees (i.e., the presence or absence of left and right children) is also identical. Essentially, for the trees to be considered identical, the entire hierarchy from the root to the leaves must be the same.

Approach

Start at the root node of both trees (p and q). First, check if both nodes are null. If both are null, the current branches are identical up to this point, so return true. If only one of them is null or if their values differ, return false, as this means the trees are not identical.
Recursively compare the left subtree of p with the left subtree of q and the right subtree of p with the right subtree of q. At each step, ensure that both the structure (presence of children) and the node values match.
If all recursive checks for the left and right subtrees return true, then the trees are identical; otherwise, if any check fails, the trees are not identical. The final result will depend on the outcome of these recursive checks.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode *left, *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // If both nodes are null, the trees are the same
        if (p == nullptr && q == nullptr) {
            return true;
        }

        // If one of the nodes is null, the trees are not the same
        if (p == nullptr || q == nullptr) {
            return false;
        }

        // If the values of the nodes are different, the trees are not the same
        if (p->data != q->data) {
            return false;
        }

        // Recursively check the left and right subtrees
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

int main() {
    // Example usage
    Solution solution;

    // Creating two sample trees
    TreeNode* tree1 = new TreeNode(1);
    tree1->left = new TreeNode(2);
    tree1->right = new TreeNode(3);

    TreeNode* tree2 = new TreeNode(1);
    tree2->left = new TreeNode(2);
    tree2->right = new TreeNode(3);

    // Checking if the trees are identical
    bool result = solution.isSameTree(tree1, tree2);
    cout << "Are the trees identical? " << result << endl;  // Output: 1 (true)

    // Clean up
    delete tree1->left;
    delete tree1->right;
    delete tree1;
    delete tree2->left;
    delete tree2->right;
    delete tree2;

    return 0;
}
// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // If both nodes are null, the trees are the same
        if (p == null && q == null) {
            return true;
        }

        // If one of the nodes is null, the trees are not the same
        if (p == null || q == null) {
            return false;
        }

        // If the values of the nodes are different, the trees are not the same
        if (p.data != q.data) {
            return false;
        }

        // Recursively check the left and right subtrees
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public static void main(String[] args) {
        // Example usage
        Solution solution = new Solution();

        // Creating two sample trees
        TreeNode tree1 = new TreeNode(1);
        tree1.left = new TreeNode(2);
        tree1.right = new TreeNode(3);

        TreeNode tree2 = new TreeNode(1);
        tree2.left = new TreeNode(2);
        tree2.right = new TreeNode(3);

        // Checking if the trees are identical
        boolean result = solution.isSameTree(tree1, tree2);
        System.out.println("Are the trees identical? " + result);  // Output: true
    }
}
class TreeNode: 
# Definition of a binary tree node
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    def isSameTree(self, p, q):
        # If both nodes are null, the trees are the same
        if not p and not q:
            return True

        # If one of the nodes is null, the trees are not the same
        if not p or not q:
            return False

        # If the values of the nodes are different, the trees are not the same
        if p.data != q.data:
            return False

        # Recursively check the left and right subtrees
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

# Example usage
if __name__ == "__main__":
    solution = Solution()

    # Creating two sample trees
    tree1 = TreeNode(1)
    tree1.left = TreeNode(2)
    tree1.right = TreeNode(3)

    tree2 = TreeNode(1)
    tree2.left = TreeNode(2)
    tree2.right = TreeNode(3)

    # Checking if the trees are identical
    result = solution.isSameTree(tree1, tree2)
    print("Are the trees identical?", result)  # Output: True
// Definition of a binary tree node  
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.data = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    isSameTree(p, q) {
        // If both nodes are null, the trees are the same
        if (!p && !q) {
            return true;
        }

        // If one of the nodes is null, the trees are not the same
        if (!p || !q) {
            return false;
        }

        // If the values of the nodes are different, the trees are not the same
        if (p.data !== q.data) {
            return false;
        }

        // Recursively check the left and right subtrees
        return this.isSameTree(p.left, q.left) && this.isSameTree(p.right, q.right);
    }
}

// Example usage
const solution = new Solution();

// Creating two sample trees
const tree1 = new TreeNode(1);
tree1.left = new TreeNode(2);
tree1.right = new TreeNode(3);

const tree2 = new TreeNode(1);
tree2.left = new TreeNode(2);
tree2.right = new TreeNode(3);

// Checking if the trees are identical
const result = solution.isSameTree(tree1, tree2);
console.log("Are the trees identical? ", result);  // Output: true

Complexity Analysis

Time Complexity: O(N) Visit each node exactly once during the traversal, where N is the number of nodes in the tree.

Space Complexity: O(h) The space complexity is determined by the recursion stack, which can go as deep as the height of the tree h.

Code

Problem List