Subtree of Another Tree
You get two binary trees, root and subRoot, each stored in an array in level order: the root at index 0, the children of index i at 2*i+1 (left) and 2*i+2 (right), and -1 for an empty spot. An array may end with extra -1 entries.
Return true if some node of root, with all of its descendants, has exactly the shape and values of subRoot, and false otherwise. The whole of root counts too.
Function
- rootinteger-array
- the tree to search, in level order with -1 for an empty spot
- subRootinteger-array
- the tree to look for, in the same format
- Returnsboolean
- true if subRoot appears in root as a node with all its descendants, false otherwise
Constraints
1 ≤ root.length ≤ 32767and1 ≤ subRoot.length ≤ 32767- Each entry is
-1or a value from0to104. root[0]andsubRoot[0]are never-1, so both trees have at least one node.- Either array may end with extra
-1entries past its last node. - Both children of an empty spot are empty too, and each tree has a depth of at most
14. - Values may repeat.
Examples
- Input
- root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
- Output
- true
- Explanation
- The node
2at index1has the children1and3, and both are leaves. That is exactlysubRoot.
- Input
- root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
- Output
- false
- Explanation
- The
3under the node2now has a child0. A subtree takes every descendant, so the node2brings four nodes against the three ofsubRoot, and no other node holds a2.
- Input
- root = [5, 5, 7]subRoot = [5]
- Output
- true
- Explanation
- The root
5has two children, so it does not match the single node5. The5at index1is a leaf and matches.
Follow-up
Can you fingerprint every subtree from its value and its children's fingerprints, so a comparison with subRoot costs O(1)? What do you do when two different subtrees collide?
Hints
Open them one at a time. Each one gives away a little more.
If
subRootappears insideroot, its top sits on one node ofroot. Which nodes could that be, and what do you check there?Write a function that says whether two trees are identical: both empty, or the same value on top with identical left subtrees and identical right subtrees. One empty spot against a real node means they differ.
Run that check from each node of
root. To skip most of them, compute every node's height first: only a node whose height equals the height ofsubRootcan match.
Solution
The problem has two parts: deciding whether two trees are identical, and choosing where in root to run that check. Only a node whose height equals the height of subRoot can match, and nodes of one height never overlap, so checking only those walks each node of root at most once.
Compare at every node
Intuition
A spot i is real when i is inside the array and the value there is not -1. Two trees are identical when both are empty, or when their tops hold the same value and their left subtrees and right subtrees are identical. same(i, j) walks root from i and subRoot from j in step. If subRoot appears in root, its top sits on some node, so try same(i, 0) from every real i.
A near match can run for up to m steps before it fails, from each of n nodes: O(n·m). Here the depth cap limits it: a node is walked only by the checks that start at it or above it, at most 14.
Algorithm
- Write
same(i, j). If the spotiinrootand the spotjinsubRootare both empty, returntrue; if exactly one is, returnfalse. - If the two values differ, return
false. Otherwise returnsame(2*i+1, 2*j+1)andsame(2*i+2, 2*j+2). - Return
trueifsame(i, 0)holds for some real indexiofroot, andfalseotherwise.
def isSubtree(root, subRoot):
n, m = len(root), len(subRoot)
def same(i, j):
# True if the subtree at root[i] equals the subtree at subRoot[j].
a = i < n and root[i] != -1
b = j < m and subRoot[j] != -1
if not a or not b:
return a == b # two empty spots match, one empty spot does not
if root[i] != subRoot[j]:
return False
return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)
# Try every real node of root as the top of a match.
for i in range(n):
if root[i] != -1 and same(i, 0):
return True
return FalseCompare only where the heights match
Intuition
Identical trees have the same height, counted as the nodes on the longest path down. So only the nodes of root whose height equals the height of subRoot are worth checking. In the first example subRoot has height 2, and in root only the 2 and the 8 do.
A node is taller than every node below it, so two nodes of equal height never sit one inside the other. Each check walks only the subtree of its start node, so the checks together walk each node of root at most once.
Children sit at larger indexes than their parent, so a scan from the last index down reaches both children before the parent. The two height scans and the checks take O(n + m) time.
Algorithm
- Fill a height array for each tree, scanning from the last index down to
0: an empty spot gets0, a real node gets1plus the larger height of its two children. - For every index
iofrootwhose height equals the height at index0ofsubRoot, runsame(i, 0)and returntrueif it holds. - Return
false.
def isSubtree(root, subRoot):
n, m = len(root), len(subRoot)
def same(i, j):
# True if the subtree at root[i] equals the subtree at subRoot[j].
a = i < n and root[i] != -1
b = j < m and subRoot[j] != -1
if not a or not b:
return a == b # two empty spots match, one empty spot does not
if root[i] != subRoot[j]:
return False
return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)
def heights(tree):
# Children sit at larger indexes, so a backward scan finishes them first.
h = [0] * len(tree)
for i in range(len(tree) - 1, -1, -1):
if tree[i] != -1:
left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
h[i] = 1 + max(left, right)
return h
target = heights(subRoot)[0]
rootHeights = heights(root)
# Only a node of the same height can match, and no two such nodes overlap.
for i in range(n):
if rootHeights[i] == target and same(i, 0):
return True
return False
Pitfalls and edge cases
- Accepting a partial match, as in the second example.
samemust fail whenroothas a node wheresubRoothas an empty spot. - Stopping at the first node with the right value. In the third example the root
5fails and the leaf5below it matches. - Comparing slices of the two arrays. A subtree's nodes are spread over many levels, and either array may end in extra
-1entries. An index past the end is an empty spot, like a-1. - In Lua and R, keep node indexes 0-based for the
2*i+1arithmetic and readroot[i + 1].
Frequently asked questions3
What is the time complexity of Subtree of Another Tree?
Comparing from every node costs O(n·m) in the worst case, where n and m are the sizes of the two trees. Comparing only at nodes whose height equals the height of subRoot brings it to O(n + m), because each node of root is then walked at most once.
Can Subtree of Another Tree be solved with string matching?
Yes. Write each tree in pre-order with # for every empty child and a separator before every value: ,2,1,#,#,3,#,#. subRoot is a subtree exactly when its string appears inside the string of root, and KMP finds it in O(n + m). Without the markers different shapes give the same string; without separators 12 contains 2.
Does a node that matches subRoot but has extra children count?
No. A subtree is a node together with all of its descendants, so every node under the match must also appear in subRoot. In the second example the extra 0 under the 3 makes the answer false.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def isSubtree(root, subRoot):
# Write code hereTest #1
Test #2
Test #3
Arguments
root = [6, 2, 8, 1, 3, -1, 9] subRoot = [2, 1, 3]
Expected Output
true