Subtree of Another Tree
EasyThe problem
Return true if the tree subRoot appears somewhere inside the tree root: some node of root, together with ALL of its descendants, must look exactly like subRoot. Otherwise return false.
- Example 1Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]Output: true
The node 4 in root has children 1 and 2, exactly like subRoot.
- Example 2Input: root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]Output: false
The node 4 in root has the same children, but the node 2 also has an extra child 0 below it, so the shapes differ.
- 1 ≤ number of nodes in root ≤ 2,000
- 1 ≤ number of nodes in subRoot ≤ 1,000
- A tree counts as a subtree of itself
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
You already wrote "are these two trees identical?". Where could the subtree start?
The idea
At every node of the big tree, check sameTree(node, subRoot). Return true if any node matches.
Target: O(n·m) time
Go function shape
func isSubtree(root *TreeNode, subRoot *TreeNode) boolReference solution
Tested with go test. Try it yourself first, then compare.
// IsSubtree: subRoot is a subtree if it is identical to the tree starting at SOME node of root.
func IsSubtree(root, subRoot *TreeNode) bool {
if root == nil {
return subRoot == nil
}
return IsSameTree(root, subRoot) || IsSubtree(root.Left, subRoot) || IsSubtree(root.Right, subRoot)
}