Subtree of Another Tree Solution in Java

Language Options

Code Solution


class Solution {
  public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null)
      return false;
    if (isSameTree(s, t))
      return true;
    return isSubtree(s.left, t) || isSubtree(s.right, t);
  }

  private boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null || q == null)
      return p == q;
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  }
}

Problem Description

The “Subtree of Another Tree” problem is like trying to find your lost sock in a pile of laundry—it’s not as easy as it sounds!
You are given two binary trees, s and t. Your mission is to determine if t is a subtree of s.
A subtree is defined as a tree that consists of a node and all of its descendants.
Imagine you’re at a family reunion, and you spot your cousin who looks just like you. You’d want to confirm if they are indeed your cousin (subtree) or just a random person (not a subtree).

Approach

The approach taken in the provided code is straightforward yet effective. The isSubtree method checks if the current node of s matches the root of t using the isSameTree helper method.
If it does, it returns true. If not, it recursively checks the left and right children of s to see if t can be found there.
The isSameTree method 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)

Real-World Example

Think of it like this: you have a big family tree (the tree s), and you want to find a specific branch (the tree t).
If you can find that branch with all its leaves intact, congratulations! You’ve found your subtree. If not, well, better luck next time!