Subtree of Another Tree

easyFREETreesBlind 75

Given the roots of two binary trees root and subRoot, return True if subRoot is a subtree of root, otherwise False.

Both trees are built from level-order arrays (with None marking a missing child) by the provided build_tree helper, so is_subtree(root, sub_root) receives TreeNode roots, not arrays.

A subtree is a node and all its descendants matching exactly.

Example

Input

3,4,5,1,2
4,1,2

Output

True

Reasoning

Inputs: root comes from the level-order array 3,4,5,1,2: $3$ is the top node, its children are $4$ (left) and $5$ (right), and $4$ has children $1$ and $2$ . sub_root comes from 4,1,2: a node $4$ with children $1$ and $2$ .
A subtree of root is not any connected piece of it: it is one node of root together with every node below it, all the way down to the leaves.
root has five candidate subtrees, one per node: rooted at $3$ (all 5 nodes), at $4$ ( $\{4, 1, 2\}$ ), and the single leaves $5$ , $1$ , $2$ .
The candidate rooted at $4$ has value $4$ on top, $1$ on the left, $2$ on the right, and nothing below $1$ or $2$ , which is exactly the shape and values of sub_root. So the answer is True.
Notice that the match must be exact to the bottom: if node $2$ in root had an extra child $0$ , the part rooted at $4$ would have four nodes, no node of root would match, and the answer would become False.

Constraints

1 <= nodes in root <= 2000
1 <= nodes in subRoot <= 1000

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The problem involves two binary trees, root and subRoot, and the goal is to determine if subRoot is a subtree of root. To approach this problem, it's essential to understand the basic structure and properties of binary trees. A binary tree is a data structure in which each node has at most two children (i.e., left child and right child). This structure allows for efficient traversal and searching of the tree.

In the context of this problem, a subtree is defined as a node and all its descendants that match exactly. This means that if subRoot is a subtree of root, then the structure and values of subRoot must be identical to a subset of nodes in root. To solve this problem, you'll need to understand how to traverse binary trees and compare their structures. Tree traversal techniques, such as pre-order, in-order, and post-order traversal, will be crucial in comparing the structures of the two trees.

The problem also involves comparing the structures of two trees, which requires understanding the concept of tree isomorphism. Two trees are isomorphic if they have the same structure, i.e., the same number of nodes and edges, and the same connections between nodes. However, in this problem, we're looking for a subtree, which means we need to find a subset of nodes in root that is isomorphic to subRoot.

Algorithm/Approach

The general approach to solving this problem involves using a combination of tree traversal and subtree comparison. One possible algorithm pattern is to traverse the root tree and, for each node, check if the subtree rooted at that node is identical to subRoot. This can be done by using a recursive function to compare the structures of the two trees.

Step-by-Step Strategy

To implement the solution, follow these steps:

Traverse the root tree using a suitable traversal method (e.g., pre-order, in-order, or post-order).
For each node in the root tree, check if the subtree rooted at that node is identical to subRoot.
To compare the structures of the two trees, use a recursive function that checks the following:

If both trees are empty, they are identical.
If one tree is empty and the other is not, they are not identical.
If the values of the current nodes are different, the trees are not identical.
If the values of the current nodes are the same, recursively compare the left and right subtrees.

If a match is found, return True, indicating that subRoot is a subtree of root.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Failing to handle the base cases correctly (e.g., when one or both trees are empty).
Not comparing the structures of the trees correctly (e.g., not checking the values of the nodes or not recursively comparing the subtrees).
Not handling the recursive function calls correctly (e.g., not returning the correct values or not terminating the recursion correctly).

Time & Space Complexity

The expected time complexity of the solution is $O(n \cdot m)$ , where $n$ is the number of nodes in the root tree and $m$ is the number of nodes in the subRoot tree. This is because, in the worst case, we need to traverse the entire root tree and compare each node with the subRoot tree. The expected space complexity is $O(h)$ , where $h$ is the height of the root tree, due to the recursive function calls.

solution.py

Python 3.13

Test results