Does One Tree Hide Inside Another
Solve this ProblemYou are given two binary trees, root and sub. Decide whether sub appears inside root: there must be a node in root such that the piece of root consisting of that node and all of its descendants is identical to sub, with the same shape and the same values. The empty tree is considered to appear in every tree.
Trying an exact comparison at every node works. You can avoid most comparisons by noticing that a matching piece must have exactly the same height as sub.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes in root ≤ 200; 0 ≤ number of nodes in sub ≤ 100 - ◆
−100 ≤ node.val ≤ 100 in both trees - ◆
Each tree is given by its root node (null for an empty tree) - ◆
Return true when some node of root has a subtree — that node together with ALL of its descendants — that is identical to sub in shape and values. An empty sub is contained in every tree
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Matching at Every Node
BruteTreat every node of root as a possible starting point. At each node, run the full "are these two trees exactly the same?" comparison against sub; if it succeeds, we are done, otherwise try the left subtree and then the right subtree of root. The comparison itself checks shape and values all the way down, so it also rejects a node whose subtree has extra descendants. In the worst case (many nodes that look like the start of sub) each of the n nodes runs a comparison of up to m steps: O(n · m) time, O(h) recursion space.
O(n · m)O(h)1class Solution {
2 public boolean containsSubtree(TreeNode root, TreeNode sub) {
3 if (sub == null) return true;
4 if (root == null) return false;
5 if (same(root, sub)) return true;
6 return containsSubtree(root.left, sub) || containsSubtree(root.right, sub);
7 }
8
9 private boolean same(TreeNode x, TreeNode y) {
10 if (x == null && y == null) return true;
11 if (x == null || y == null) return false;
12 return x.val == y.val && same(x.left, y.left) && same(x.right, y.right);
13 }
14}Optimal — Only Compare Nodes Whose Height Equals sub's Height
OptimalCompute the height of sub once. Then walk root bottom-up, computing each node's height as you return. If a subtree is identical to sub, it must have exactly the same height — so only nodes of that height need the expensive comparison; every other node is skipped. The key fact: a node can never contain another node of the same height inside it (its children are strictly shorter), so the subtrees of all equal-height nodes are disjoint and their comparisons add up to at most n steps in total. Together with the m steps for sub's own height, that is O(n + m) time and O(h) space.
O(n + m)O(h)1class Solution {
2 private boolean found;
3
4 public boolean containsSubtree(TreeNode root, TreeNode sub) {
5 if (sub == null) return true;
6 found = false;
7 walk(root, sub, height(sub));
8 return found;
9 }
10
11 private int height(TreeNode node) {
12 if (node == null) return 0;
13 return 1 + Math.max(height(node.left), height(node.right));
14 }
15
16 private int walk(TreeNode node, TreeNode sub, int target) {
17 if (node == null) return 0;
18 int h = 1 + Math.max(walk(node.left, sub, target), walk(node.right, sub, target));
19 if (h == target && same(node, sub)) found = true;
20 return h;
21 }
22
23 private boolean same(TreeNode x, TreeNode y) {
24 if (x == null && y == null) return true;
25 if (x == null || y == null) return false;
26 return x.val == y.val && same(x.left, y.left) && same(x.right, y.right);
27 }
28}