Subtree of Another Tree LeetCode 572

LeetCode 572 — Subtree of Another Tree — gives you the roots of two binary trees, root and subRoot, and asks you to return true if there exists a subtree of root with the same structure and node values as subRoot. A subtree of a binary tree consists of a node and all of its descendants. The tree root itself is also considered a subtree of root.

This problem builds directly on LeetCode 100 — Same Tree — and is an excellent example of problem decomposition: breaking a complex question into two simpler recursive functions that each do one thing well. Understanding how to compose isSubtree and isSameTree is a key interview pattern for tree problems.

The constraints define the search space: root can have up to 2,000 nodes and subRoot up to 1,000 nodes. Node values are integers between -10,000 and 10,000. An empty subRoot is considered a subtree of any tree, but LeetCode guarantees subRoot is non-null in the official test cases.

The recursive solution traverses every node in root and asks: does the subtree rooted at this node match subRoot exactly? If any node passes this test, return true immediately. If no node matches after traversing all of root, return false. This is a pre-order traversal of root combined with a full comparison at each stop.

The outer function isSubtree handles the traversal: if root is null, return false (no match possible in an empty tree); if isSameTree(root, subRoot) is true, return true immediately; otherwise recurse into root.left and root.right with isSubtree, returning true if either side finds a match. The logical OR short-circuits as soon as a match is found.

The time complexity is O(m * n) in the worst case, where m is the number of nodes in root and n is the number of nodes in subRoot. For each of the m nodes in root, isSameTree may inspect up to n nodes of subRoot. Space complexity is O(max(h1, h2)) for the recursion stack, where h1 and h2 are the heights of root and subRoot respectively.

The isSameTree helper compares two trees recursively and returns true only if they have identical structure and identical node values at every position. It has three base cases and one recursive case, making it one of the most concise and elegant tree functions you will write.

The logic is symmetric: if both nodes are null, we have reached matching leaf positions and return true. If exactly one is null, the structures diverge and we return false. If both are non-null but their values differ, return false. Otherwise, the current nodes match and we recurse on both left and right children, returning true only if both pairs match.

In Python: def isSameTree(p, q): if not p and not q: return True; if not p or not q: return False; return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right). In Java, the same logic uses ternary chains or explicit if-statements. The short-circuit evaluation of "and" means we stop at the first mismatch.

The O(m * n) complexity arises because isSubtree visits every node in root — that is m nodes — and at each node calls isSameTree, which in the worst case traverses all n nodes of subRoot. Multiplying these two traversals gives O(m * n) total operations in the theoretical worst case.

The worst case occurs with a pathological input: a highly skewed root tree where every node has the same value as subRoot's root, but only the very last node of root actually matches subRoot completely. In this scenario isSameTree runs nearly to completion at every node of root before finding a mismatch, giving true O(m * n) behavior.

For typical balanced trees and dissimilar subtrees, the actual performance is far better because isSameTree short-circuits at the very first value mismatch. If subRoot has a distinctive root value that rarely appears in root, most calls to isSameTree return false after comparing just one node, making the practical complexity closer to O(m).

The serialization approach converts both trees into string representations and then checks whether subRoot's serialization is a substring of root's serialization. If it is, subRoot is a subtree of root; if not, it is not. This reduces the problem to string matching, which can be solved in O(m + n) time using the KMP (Knuth-Morris-Pratt) algorithm.

Serialization must use null markers and delimiters to avoid false positives. Without markers, the tree with a single node valued 12 would serialize to "12" and the single-node tree valued 2 would serialize to "2" — and "2" is a substring of "12" even though neither is a subtree of the other. A safe format: separate each value with a comma and represent null nodes with "#", e.g., "1,2,3,#,#,#,#".

The serialization approach uses O(m + n) time for the serialization step and O(m + n) time for KMP matching, giving O(m + n) overall. Space is O(m + n) for the serialized strings. This is asymptotically superior to the recursive O(m * n) approach, though in practice the recursive solution is simpler to code and explain in an interview setting.

Python recursive solution: def isSubtree(root, subRoot): if not root: return False; if isSameTree(root, subRoot): return True; return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot). Helper: def isSameTree(p, q): if not p and not q: return True; if not p or not q: return False; return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right). This is clean, interview-standard, and fits on one screen.

Java recursive solution: public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (root == null) return false; if (isSameTree(root, subRoot)) return true; return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); } private boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; if (p == null || q == null) return false; return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }. Identical logic, idiomatic Java style.

Both versions run in O(m * n) time and O(max(h1, h2)) space for the recursion stack. The recursive approach is the standard answer in interviews: it is concise, demonstrates problem decomposition, and is easy to reason about correctness. Mention the serialization O(m + n) alternative if the interviewer asks about optimization or if the tree has up to 10^4 nodes where the constant factor matters.

Same Tree (LeetCode 100) is the direct building block for this problem — isSameTree is extracted verbatim and called as a helper. Understanding Same Tree deeply makes Subtree of Another Tree almost trivial, which is why these two problems are studied together in every serious interview prep curriculum.

Symmetric Tree (LeetCode 101) also uses the isSameTree mental model but compares the left and right subtrees of a single tree against each other in mirror fashion. Invert Binary Tree (LeetCode 226) rounds out the structural manipulation family. Together, Same Tree, Symmetric Tree, Invert Binary Tree, and Subtree of Another Tree form the tree comparison and transformation quartet that every tree section covers.

For deeper exploration, Binary Tree Maximum Path Sum (LeetCode 124) and Count Good Nodes (LeetCode 1448) both require post-order aggregation patterns that build on the same recursive thinking. Once you are comfortable composing isSubtree with isSameTree, you have the mental model needed to compose any two tree functions together for more complex problems.