Solving Subtree of Another Tree: Comparing Tree Structures

The "Subtree of Another Tree" problem involves determining whether one binary tree is a subtree of another binary tree.

Problem Statement

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of tree s.

Example

Consider two binary trees s and t:

Tree t is a subtree of tree s.

Solution Approach - Recursive Comparison

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function isSubtree(s: TreeNode | null, t: TreeNode | null): boolean {
  if (!s) return !t;
  return isSameTree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}

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

Breaking Down the Solution

• Recursive Tree Comparison: The function isSameTree checks if two trees are identical.
• Subtree Check: The function isSubtree checks if t is the same as s, or if t is a subtree of either the left or right subtree of s.
• Base Cases: Handle null trees appropriately in both functions.

Conclusion

The Subtree of Another Tree problem is an interesting application of binary tree algorithms, requiring a combination of tree traversal and recursive comparison to determine subtree relationships.