Subtree of Another Tree
EasyTrees
Given the roots of two binary trees, root and subRoot, return true if some node of root, together with everything below it, is the same tree as subRoot, and false otherwise. The whole of root counts too.
Same means the same shape with the same values: the node you pick must have nothing below it that subRoot lacks.
On this page a tree is written in level order, top to bottom and left to right, with null where a child is missing: [6, 3, 8, 1] is 6 with children 3 and 8, and 3 with a left child 1.
Examples
Input: root = [8, 2, 5, null, 6, 3, 1], subRoot = [5, 3, 1] Output: true
The node 5, with its children 3 and 1, is exactly subRoot.
Input: root = [6, 2, 8, 1, 3], subRoot = [2, 1] Output: false
The node 2 has children 1 and 3, and subRoot has no 3, so the tree under 2 is not the same.
Constraints
roothas 1 to 2000 nodes, andsubRoothas 1 to 1000.-10⁴ ≤ node.val ≤ 10⁴
Stuck?
Hint 1
Every node of root is a place subRoot could start. At each one, ask whether the tree hanging from it is the same as subRoot.
Hint 2
Write a helper that tells whether two trees are the same, and call it at every node as you walk root. When a value matches but the trees differ, keep walking: a later node may still match.
The idea
Any node of root could be where subRoot starts, so try every one. At each node, ask whether the tree hanging from it is exactly the same as subRoot, which is the same-tree check.
Time O(m · n) for trees of m and n nodesExtra space O(h) for a tree of height h
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 3
same tells whether two trees match exactly: both empty, or both there with equal values and matching left and right subtrees. A node of root with extra children below it fails here.
function isSubtree(root, subRoot) { const same = (a, b) => { if (!a && !b) return true; if (!a || !b || a.val !== b.val) return false; return same(a.left, b.left) && same(a.right, b.right); }; if (!root) return false; return same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);}The trap
Calling the full comparison where the values match is right, but returning its answer there ends the search too early. If a node has subRoot's value but a different tree below it, the function answers false without looking under that node, where the real match may sit. Trees that repeat a value on the way down to the match break it.
function isSubtree(root, subRoot) { const same = (a, b) => { if (!a && !b) return true; if (!a || !b || a.val !== b.val) return false; return same(a.left, b.left) && same(a.right, b.right); }; if (!root) return false; if (root.val === subRoot.val) return same(root, subRoot); // stops at the first matching value return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);}