DEV Community

Dev Cookies
Dev Cookies

Posted on

🌳 Blog 6: Subtree & Structure Matching in Binary Trees

🔍 Why This Pattern?

Some problems don’t care about values along a path but instead about tree structure itself:

  • Is one tree a subtree of another?
  • Are two trees identical?
  • Is the tree symmetric (mirror)?
  • Serialize & compare structures.

This pattern focuses on recursive structure matching.

🛠 Core Idea (Template) 

boolean isSame(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    return p.val == q.val 
        && isSame(p.left, q.left) 
        && isSame(p.right, q.right);
}
Enter fullscreen mode Exit fullscreen mode

This “isSame” helper is the foundation for many subtree/structure problems.

✅ Classic Problems

1. Same Tree (LeetCode 100)

Check if two trees are identical.
Uses the template above.

2. Subtree of Another Tree (LeetCode 572)

Check if subRoot is a subtree of root.

  • Traverse root.
  • At each node, check if subtree matches using isSame. 
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (isSame(root, subRoot)) return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSame(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return p.val == q.val 
            && isSame(p.left, q.left) 
            && isSame(p.right, q.right);
    }
}
Enter fullscreen mode Exit fullscreen mode

3. Symmetric Tree (LeetCode 101)

Check if tree is mirror of itself.

  • Compare left subtree and right subtree in mirrored fashion. 
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val)
            && isMirror(t1.left, t2.right)
            && isMirror(t1.right, t2.left);
    }
}
Enter fullscreen mode Exit fullscreen mode

4. Flip Equivalent Trees (LeetCode 951)

Check if two trees are the same when flipping children allowed.

class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null || root1.val != root2.val) return false;

        return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
               (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
    }
}
Enter fullscreen mode Exit fullscreen mode

🚀 Advanced Variations

  1. Serialize & Deserialize Tree (LeetCode 297)
  • Store structure as string (preorder + null markers).
  • Useful for comparing subtrees with hashing/string matching.
  1. Count Subtrees Matching a Condition
  • E.g., count number of identical subtrees, or count symmetric subtrees.
  1. Check Isomorphic Trees
  • Allow flipping left/right at any level and still consider identical.

🎯 Quick Pattern Checklist

  • ✅ If problem asks for identical/same tree → recursion with isSame().
  • ✅ If problem asks for subtree check → recursion + isSame().
  • ✅ If problem asks for mirror/symmetric check → recursion comparing mirrored children.
  • ✅ If problem asks for flip equivalence/isomorphism → allow swap of children during check.

🔥 Key Takeaway:
Subtree & structure matching problems are solved using recursive comparison.
Master isSame() and its mirrored/flip variations — you’ll crack almost every such question.

Top comments (0)