Problem overview
isSubtree receives two optional TreeNode values, root and subRoot, and returns a Bool. The answer is true when some node of root, taken together with all of its descendants, forms exactly the same tree as subRoot: same shape and the same value in every place. A tree counts as a subtree of itself. The lesson provides the TreeNode class, with val, left and right and an init(_ x: Int).
In the first example, root = [3,4,5,1,2] and subRoot = [4,1,2]. The node 4 of root has the children 1 and 2 and nothing else, so it matches and the answer is true. In the second example, the 2 has an extra child 0 in root. The node 4 now carries more than subRoot does, and a subtree must take every descendant, so the answer is false.
Approach: compare at every node
The idea splits the problem in two. First, a way to tell whether two trees are identical: walk both together, and they match when both are empty, or when both roots hold the same value and the left subtrees match and the right subtrees match. Second, a way to try that comparison at every possible starting place: the match is either at root itself, or inside its left subtree, or inside its right subtree.
With n nodes in root and m in subRoot, the comparison at one node stops after at most m nodes, since a comparison can't go deeper than subRoot does, and it is started at each of the n nodes. That gives O(n · m) time, which is the budget the lesson sets.
Step by step
- Base case of
isSubtree. Unwraprootwithguard letand returnfalsewhen it isnil. An empty tree has no node wheresubRootcould begin, andsubRoothas at least one node. This also ends the recursion when it steps below a leaf. - Try the current node. If the helper says
rootandsubRootare the same tree, returntrueat once. - Try lower down. Otherwise return whether
subRootis a subtree ofroot.leftor ofroot.right, joined with||. Together with step 2, every node ofrootgets tried as the starting point. - Write the helper's signature.
isSameTreetakes twoTreeNode?parameters,pandq, without argument labels, and returnsBool. - Both empty. If
pandqare bothnil, the trees are equal. This is where the recursion ends when both sides run out together. - Only one empty. Unwrap both with one
guard let. If either isnil, the case of both being empty has already returned, so exactly one is empty and the shapes differ: returnfalse. - Different values. Both nodes exist now, so compare
p.valwithq.valand returnfalseif they differ. - Compare the children. The roots match, so the trees are equal exactly when the left pair and the right pair are equal: two recursive calls joined with
&&.
The solution in Swift
class Solution {
func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
if p == nil && q == nil {
return true
}
guard let p = p, let q = q else {
return false
}
if p.val != q.val {
return false
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}
func isSubtree(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
guard let root = root else {
return false
}
if isSameTree(root, subRoot) {
return true
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
}
}
The Swift details worth a closer look:
guard let root = rootcreates a new, non-optional constant namedrootthat hides the optional parameter for the rest of the function. Theelseblock must leave the function, here withreturn false. After the guard,root.leftandroot.valneed no?or!.p == nilworks withoutEquatable.TreeNodeis a plain class, but Swift lets any optional be compared withnil. What this does not do is compare two nodes: the lesson compares values and shape, never identity, so there is no===here.- Short-circuit operators.
&&skips its right side when the left one isfalse, and||skips the right side when the left one istrue. A comparison stops at the first difference, and the search stops at the first match. - Passing optionals along.
isSameTree(root, subRoot)passes aTreeNodewhere aTreeNode?is expected, which Swift wraps automatically. - Methods call each other by name. Inside a class,
isSameTreeandisSubtreecall themselves and each other withoutself., and their order in the class doesn't matter.
Complexity
Time: O(n · m). isSubtree visits each of the n nodes of root once. At each, isSameTree runs for at most m steps, because it ends when subRoot's nodes are used up or a difference shows.
Space: O(h) for the call stack, where h is the depth of root (at most 400 in this lesson). The code allocates nothing else.
Edge cases and common mistakes
- Matching only the top of the subtree. Comparing just the roots' values, or stopping when
subRootruns out, accepts a node that has extra descendants. The second example is that trap: the 4 with 1 and 2 under it looks right until the 0 below the 2 is reached. Requiring both sides to benilat the same moment is what rejects it. - Checking
rootitself only. The match can be anywhere, so the recursion must continue into both children when the current node fails. - Equal values, different shapes. With
root = [1,1]andsubRoot = [1], the top 1 has a child, so it doesn't match, but its left child is a lone 1 and does. The answer istrue. - Same values, different shape. With
root = [1,2]andsubRoot = [2,nil,3]the value 2 appears in both, but the 2 inrootis a leaf and the one insubRoothas a right child. Comparing thenilchildren in the right places tells them apart, and the answer isfalse.
Testing
root = [3,4,5,1,2],subRoot = [4,1,2]givestrue.root = [3,4,5,1,2,nil,nil,nil,nil,0],subRoot = [4,1,2]givesfalse.root = [1,1],subRoot = [1]givestrue.root = [1],subRoot = [1]givestrue, since a tree is a subtree of itself.root = [1,2],subRoot = [2,nil,3]givesfalse.root = [1,nil,2,nil,3],subRoot = [3]givestrue: the leaf 3 at the bottom of a right-leaning chain.
