algoadvance

Leetcode 100. Same Tree

Problem Statement

Given two binary trees, 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:

Input:

    Tree 1:     1         Tree 2:     1
               / \                  / \
              2   3                2   3

Output: true

Clarifying Questions

  1. What should be returned if both trees are empty?
    • Return true because two empty trees are considered the same.
  2. What does the function need to return if only one of the trees is empty?
    • Return false because an empty tree cannot be structurally identical to a non-empty tree.
  3. Can the nodes have negative values?
    • Yes, nodes can have any integer value.
  4. Is there a constraint on the tree’s height or number of nodes within the tree?
    • The problem statement does not specify any constraints, so general solutions should handle typical binary trees.

Strategy

  1. Recursive Approach:
    • If both trees are empty, return true.
    • If one of the trees is empty and the other is not, return false.
    • Recursively compare the root values of both trees.
    • Recursively compare the left subtrees.
    • Recursively compare the right subtrees.

    If all these conditions are met, the trees are the same.

Code

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // If both trees are null, they are same
        if (!p && !q) return true;
        // If one of them is null, they are not same
        if (!p || !q) return false;
        // If values of current nodes are different, they are not same
        if (p->val != q->val) return false;
        // Recursively check left and right subtrees
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree. This is because each node is visited once.

Space Complexity: O(h), where h is the height of the trees. This is the maximum depth of the recursion stack.

The provided solution correctly determines if two binary trees are the same by using a recursive function. Each step involves checking the node values and recursively checking the left and right subtrees for equality.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI