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 equal. If not, 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). Both recursive calls must return true for the trees to be considered the same.

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 have the same value. The recursive calls systematically compare corresponding subtrees. If at any point a mismatch is found (either in node values or subtree structure), the function immediately returns false. Only if all corresponding nodes have the same values and the structure is identical will the function ultimately return true.

Code

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        // 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;

        // Value Check: Values must be equal.
        if (p.val != q.val) return false;

        // Recursive Calls: Check left and right subtrees.
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
    }
}

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, 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 could be equal to N. In the best case (a balanced tree), H would be logâ‚‚(N).