algoadvance

Leetcode 572. Subtree of Another Tree

Problem Statement

You are given the roots of two binary trees root and subRoot. Write a function to determine if subRoot is a subtree of root.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

Clarifying Questions

  1. What is the structure of the binary trees?
    • The trees are given as arrays in level-order format.
  2. Can either of the trees be empty?
    • If subRoot is empty, it is trivially a subtree of any tree. If root is empty and subRoot is not, it is trivially false.
  3. What should be returned?
    • The function should return a boolean: true if subRoot is a subtree of root, otherwise false.

Strategy

  1. Traversal and Comparison:
    • The problem can be approached by traversing the root tree and, at each node, checking if the subtree rooted at this node matches subRoot.
    • This requires two main functions:
      1. isSameTree: This will determine if two trees are identical.
      2. isSubtree: This will recursively traverse the root tree and use isSameTree to check for subtree matches.
  2. Recursive Approach:
    • Traverse every node in the root tree using recursion.
    • At each node, call isSameTree to check if the subtree rooted at this node matches subRoot.
    • If a match is found, return true.
    • If no match is found after checking all nodes, return false.

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 isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root) return !subRoot;
        if (isSameTree(root, subRoot)) return true;
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }

    bool isSameTree(TreeNode* s, TreeNode* t) {
        if (!s && !t) return true;
        if (!s || !t) return false;
        if (s->val != t->val) return false;
        return isSameTree(s->left, t->left) && isSameTree(s->right, t->right);
    }
};

int main() {
    // Example usage:
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(4);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(2);
    
    TreeNode* subRoot = new TreeNode(4);
    subRoot->left = new TreeNode(1);
    subRoot->right = new TreeNode(2);
    
    Solution sol;
    std::cout << (sol.isSubtree(root, subRoot) ? "true" : "false") << std::endl; // Output: true
    
    // Clean up
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;
    delete subRoot->left;
    delete subRoot->right;
    delete subRoot;
    
    return 0;
}

Time Complexity

This strategy ensures that we efficiently traverse and compare subtrees to determine if subRoot is a subtree of root.

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