Same Tree easy

Problem Statement

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

Steps

1. Base Case: If both p and q are null, they are the same, return true. If only one of them is null, they are different, return false.

2. Value Check: Check if the values of the root nodes p.val and q.val are different. If they are, return false.

3. Recursive Calls: Recursively call the isSameTree function for the left subtrees (p.left, q.left) and the right subtrees (p.right, q.right). If both recursive calls return true, then the trees are the same. Otherwise, they are different.

Explanation

The solution uses a recursive approach to compare the trees. The base case handles the scenario where one or both trees are empty. The value check ensures that the root nodes match. The recursive calls systematically compare the left and right subtrees, ensuring that the entire structure and values are identical. If any mismatch is found at any level, the function immediately returns false.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    // Base Case: Both null, they are the same
    if (p === null && q === null) {
        return true;
    }
    // Base Case: One null, the other not, they are different
    if (p === null || q === null) {
        return false;
    }
    //Check if root values are different
    if (p.val !== q.val) {
        return false;
    }
    // Recursive calls for left and right subtrees
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}


// Example usage:
const p1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
const q1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(isSameTree(p1, q1)); // Output: true

const p2 = new TreeNode(1, new TreeNode(2));
const q2 = new TreeNode(1, null, new TreeNode(2));
console.log(isSameTree(p2, q2)); // Output: false

const p3 = null;
const q3 = null;
console.log(isSameTree(p3,q3)); // Output: true

const p4 = new TreeNode(1);
const q4 = null;
console.log(isSameTree(p4,q4)); //Output: false

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is log(N).