Subtree of Another Tree Solution in C++

Problem Description

So, you think you can just waltz into a binary tree and find a subtree? Well, welcome to the world of “Subtree of Another Tree,” where trees are like your relatives at a family reunion—some are just too similar, and some are just too different!

Imagine you have a big tree (let’s call it Tree S) that’s like your family tree, and then you have a smaller tree (Tree T) that’s like your cousin’s family tree. The question is: can you find your cousin’s family tree hiding somewhere in your family tree? Spoiler alert: it’s not as easy as it sounds!

In technical terms, you need to determine if Tree T is a subtree of Tree S. A subtree is defined as a tree that consists of a node and all of its descendants. So, if you can find a node in Tree S that matches the root of Tree T and all of its children match as well, congratulations! You’ve found a subtree!

Code Solution


class Solution {
 public:
  bool isSubtree(TreeNode* s, TreeNode* t) {
    if (s == nullptr)
      return false;
    if (isSameTree(s, t))
      return true;
    return isSubtree(s->left, t) || isSubtree(s->right, t);
  }

 private:
  bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p || !q)
      return p == q;
    return p->val == q->val &&              //
           isSameTree(p->left, q->left) &&  //
           isSameTree(p->right, q->right);
  }
};

Approach

The approach taken in this solution is straightforward yet effective. The isSubtree function checks if the current node in Tree S matches the root of Tree T using the helper function isSameTree. If it does, it returns true. If not, it recursively checks the left and right children of Tree S. The isSameTree function checks if two trees are identical by comparing their values and recursively checking their left and right children.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * M)
Space Complexity	O(H)

Time Complexity: O(N * M), where N is the number of nodes in Tree S and M is the number of nodes in Tree T. In the worst case, we may have to check every node in Tree S against every node in Tree T.

Space Complexity: O(H), where H is the height of Tree S. This is due to the recursion stack.

Real-World Example

Think of it like this: you’re trying to find a specific recipe (Tree T) in a massive cookbook (Tree S). You flip through the pages (nodes) and check if the recipe matches. If you find a page that looks like your recipe, you check the ingredients and instructions (children) to see if they match perfectly. If they do, you’ve found your recipe! If not, you keep flipping through the pages until you either find it or give up and order takeout.