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)