LietCode
Same Tree (Easy)

Same Tree (Easy)

Abhi's photo
Abhi
·

3 min read

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.

Example 1:

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

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

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

1) Explain the problem

We need to check if two binary trees are the same. Two binary trees are considered the same if they have the same structure and the same node values.

2) Short easy to remember solution/approach

Use a depth-first search (DFS) approach to simultaneously traverse both trees and compare the corresponding nodes. Return false if any discrepancy is found.

3) Solution in Javascript with code commenting

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function isSameTree(p, q) {
    // If both nodes are null, they are the same
    if (p === null && q === null) return true;

    // If one of the nodes is null or their values are different, they are not the same
    if (p === null || q === null || p.val !== q.val) return false;

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

// Example usage:
let tree1 = new TreeNode(1);
tree1.left = new TreeNode(2);
tree1.right = new TreeNode(3);

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

console.log(isSameTree(tree1, tree2)); // Output: true

4) Explanation of the solution in an easy-to-understand way. Explain it like a 10-year-old.

Imagine you have two sets of LEGO trees. To check if they are exactly the same, you start from the top and look at each piece. If you find any difference in pieces or structure as you go through both trees, then they are not the same. Otherwise, they are identical.

5) Code explanation in pointers

  • Define a TreeNode class to represent each node in the tree.

  • Create an isSameTree function that:

    • Returns true if both nodes are null.

    • Returns false if one node is null or their values differ.

    • Recursively checks the left and right subtrees for both trees.

  • Use the isSameTree function to compare the trees starting from their roots.

6) Complexities

  • Time Complexity: (O(n)) - Each node in both trees is visited once.

  • Space Complexity: (O(h)) - Where (h) is the height of the trees. This is due to the recursion stack.

Tree