Problem overview
The method isSubtree receives the roots of two binary trees, root and subRoot. It returns true when some node of root, together with all of its descendants, forms exactly the same tree as subRoot: same shape and same value in every position. A tree counts as a subtree of itself. The lesson provides the TreeNode struct, with an int val, two pointers left and right, and a constructor that takes the value and sets both pointers to NULL.
In the first example, root = [3,4,5,1,2] and subRoot = [4,1,2]. The node 4 of root has children 1 and 2, which is exactly subRoot, so the answer is true. In the second example, root is [3,4,5,1,2,NULL,NULL,NULL,NULL,0]: the 2 now has a child 0. The node 4 still has 1 and 2 below it, but a subtree takes every descendant, so the tree under 4 is bigger than subRoot and the answer is false.
Approach: try every node of root as the starting point
The question splits into two smaller ones:
- Given two trees, are they identical?
- Is there a node of
rootwhere the tree below it is identical tosubRoot?
The first question is the classic "same tree" check, a short recursion that walks both trees at once. The second is answered by visiting every node of root and asking the first question there. A node can only be the start of a match if its whole tree equals subRoot. Otherwise the match, if any, begins lower: in the left subtree or in the right subtree.
Comparing subRoot with the tree at one node of root stops as soon as the trees differ, and it never looks at more than m nodes, where m is the size of subRoot, because a match must have the same number of nodes. With n nodes in root and one comparison started at each, the total is O(n · m). That is what the lesson asks for. Faster methods exist, such as serializing both trees and searching for one string inside the other, but they need more machinery than this lesson uses.
Step by step
The lesson writes isSubtree first, assuming a helper isSameTree exists, and then writes the helper.
- Stop on an empty tree. If
rootisnullptr(!root), returnfalse.subRoothas at least one node, so an empty tree can't contain it. This check also ends the recursion when the search steps below a leaf. - Check the current node. If
isSameTree(root, subRoot)is true, returntrue: the match starts right here. - Search lower down. Otherwise return
isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot). Together with step 2, this tries every node ofrootas the place wheresubRootstarts. The||skips the right side when the left side has already found a match. - Declare the helper.
isSameTreetakes twoTreeNode*parameters,pandq, and returnsbool. It goes aboveisSubtreein the class. - Both empty means equal. If
!p && !q, returntrue. This is the base case when both trees run out at the same time. - One empty means different. If
!p || !q, returnfalse. The case where both are empty already returned in the previous step, so here exactly one of them is empty: the shapes differ. - Compare the values. If
p->val != q->val, returnfalse. Both pointers are known to be non-null at this point, so readingvalis safe. - Compare the children. Return
isSameTree(p->left, q->left) && isSameTree(p->right, q->right). The roots match, so the trees are the same exactly when both pairs of subtrees are.
The solution in C++
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) {
return true;
}
if (!p || !q) {
return false;
}
if (p->val != q->val) {
return false;
}
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (!root) {
return false;
}
if (isSameTree(root, subRoot)) {
return true;
}
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
};
The C++ details worth a closer look:
- Pointers in conditions. A pointer converts to
bool: a null pointer isfalseand any other pointer istrue. So!rootmeans "root is null", and!p && !qmeans "both are null". - Arrow versus dot.
p->valreads a member through a pointer. Dereferencing a null pointer is undefined behaviour, which is why the null checks come before every->. - Short-circuit evaluation. In
a && b,bis not evaluated whenais false, and ina || b,bis skipped whenais true. Besides saving work, this is what keeps a comparison from continuing after the first difference. - Member order. Inside a class, a member function can call another one that is written later, so
isSubtreecould also come first. The lesson puts the helper above to read top to bottom. - Nothing is changed or freed. The method only reads the trees, so it leaves them as they were and the caller still owns every node.
Complexity
Time: O(n · m). isSubtree reaches each of the n nodes of root at most once. At each one, isSameTree visits at most as many node pairs as subRoot has nodes, m, since a pair is only visited while both trees still have a node there. That gives at most n · m steps in all, and usually far fewer, because most comparisons fail at the first few nodes.
Space: O(h) for the recursion stack, where h is the height of root. isSubtree goes at most h calls deep, and a comparison started at a node goes no deeper than the part of root below that node, so the two together stay within about 2h. For a degenerate tree that is a single chain, h can be as large as n.
Edge cases and common mistakes
- The whole tree. A tree is a subtree of itself, so
root = [3,4,5,1,2]with the samesubRootreturnstrueat the first comparison. - Extra descendants. Matching the values of
subRootsomewhere insiderootis not enough. In the second example, 4, 1 and 2 are all present, but the 0 below the 2 makes the tree under 4 different. A check that only compares the top levels gives the wrong answer. - A single-node
subRoot. Withroot = [1,1]andsubRoot = [1], the root 1 has a child, so the tree under it is notsubRoot. Its left child 1 has nothing below it, so that subtree matches and the answer istrue. The search has to continue past a failed root. - Forgetting the base case. Without
if (!root) return false;, the recursion eventually passes a null child toisSameTreeand then to->lefton a null pointer. - Mixing up the two empty cases. Both null means equal and exactly one null means different. Testing
!p || !qbefore!p && !qwould report two empty trees as different. - Comparing only values. Two trees with the same values in a different shape are different. That is why a null child has to be compared with a null child, not skipped.
Testing
Trees are written in level order, with NULL for a missing child.
root = [3,4,5,1,2],subRoot = [4,1,2]givestrue.root = [3,4,5,1,2,NULL,NULL,NULL,NULL,0],subRoot = [4,1,2]givesfalse.root = [1,1],subRoot = [1]givestrue.root = [1,2],subRoot = [2,3]givesfalse.root = [1,NULL,1],subRoot = [1]givestrue.root = [3,4,5,1,2],subRoot = [5,1]givesfalse.root = [4,1,2],subRoot = [3,4,5,1,2]givesfalse:subRootis bigger thanroot.
