Start learning free

LESSON 422 OF 543 · BINARY TREES

Subtree of Another Tree in Rust: O(n·m) with Recursion

Practice O(n · m) Read the full explanation

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

A subtree of a tree is a node of that tree together with all of its descendants. subRoot is a subtree of root when some node of root and everything below it form exactly the same tree as subRoot: the same shape and the same value in every place. A tree is also a subtree of itself.

The trees below are written in level order (top to bottom, left to right), with None for a missing child.

Example 1:

      root        subRoot
       3             4
      / \           / \
     4   5         1   2
    / \
   1   2

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Explanation: The node 4 of root, with its children 1 and 2, is the same tree as subRoot.

Example 2:

      root        subRoot
       3             4
      / \           / \
     4   5         1   2
    / \
   1   2
      /
     0

Input: root = [3,4,5,1,2,None,None,None,None,0], subRoot = [4,1,2]
Output: false
Explanation: The node 4 of root has 1 and 2 below it, but the 2 has a child 0 that subRoot doesn't have. A subtree takes every descendant of its node, so no node of root gives the tree subRoot.

Example 3:

Input: root = [1,1], subRoot = [1]
Output: true
Explanation: The root 1 has a child, so the tree under it isn't subRoot. Its left child 1 has nothing below it: that subtree is the same as subRoot.

Constraints:

The number of nodes in root is in the range [1, 2000].
The number of nodes in subRoot is in the range [1, 1000].
Each node value is between -10⁴ and 10⁴.
Each tree is at most 400 levels deep.

Note:

Your algorithm should run in O(n · m) time, where n and m are the numbers of nodes in root and subRoot: compare subRoot with the tree under each node of root, as in Same Tree. Each comparison stops after at most m nodes.

STEP 1 OF 12

Guided

Ctrl + Enter to check

RUST · BINARY TREES

Subtree Of Another Tree in Rust, explained

Problem overview

is_subtree receives two binary trees, root and sub_root, and answers whether sub_root appears inside root. "Appears" has a strict meaning here: some node of root, together with all of its descendants, must have exactly the same shape and the same values as sub_root. A tree counts as a subtree of itself.

In the first example, root is [3,4,5,1,2] and sub_root is [4,1,2]. The node 4 of root has the children 1 and 2, and nothing else below it, so the answer is true. In the second example the 2 has an extra child 0. The tree under node 4 is now bigger than sub_root, and no other node fits either, so the answer is false. In the third, root = [1,1] and sub_root = [1]: the root 1 has a child, so it doesn't match, but its left child 1 is a leaf and does.

Both trees arrive as &Option<Box<TreeNode>>. The lesson provides TreeNode, with the fields val, left and right, so you don't define it. The references matter: the search compares sub_root with many parts of root, so it must only borrow the trees.

Approach: compare at every node

The statement asks for O(n · m) time, where n and m are the sizes of the two trees. That suggests the simplest plan: treat each node of root as a possible starting point and ask "is the tree here the same as sub_root?". The question is a smaller problem of its own, comparing two trees for equality, and it has a natural recursive answer.

Two trees are the same when:

both are empty, or
both have a node, the two values are equal, and the left subtrees are the same, and the right subtrees are the same.

Anything else, including one empty tree and one non-empty tree, is a mismatch. With that helper, is_subtree is a second recursion: the answer is true if the trees are the same right here, or if sub_root is a subtree of the left child, or of the right child. An empty root contains nothing, since sub_root has at least one node.

The cost: one comparison starts at each of the n nodes of root, and a comparison can't go past the nodes of sub_root, so it stops after at most m steps. That is O(n · m).

Step by step

Start with a match on root. Its value, with no semicolon after the closing brace, is what the function returns.
The None arm returns false. An empty tree has no node where sub_root could start. This is also where the recursion ends when it steps below a leaf.
The Some(node) arm gets a block body. Because root is a reference, node is borrowed too, so reading node.left doesn't move anything.
Compare here first. If Self::is_same_tree(root, sub_root) is true, return true at once.
Otherwise search below. The arm ends with the left subtree check || the right subtree check. The || skips the right side when the left side already found a match.
Write the helper is_same_tree above it, with two borrowed trees p and q.
Match on the pair (p, q) so one arm can look at both trees together.
(None, None) is true. Two empty trees are equal, and this ends the recursion when both sides pass a leaf at once.
(Some(p), Some(q)) rebinds p and q to the nodes themselves, so p.val and p.left work directly.
Return false early when the values differ.
End the arm with the two recursive calls joined by &&: the left subtrees must match and so must the right ones.
The last arm, _ => false, covers the case where exactly one tree is empty. Rust requires a match to handle every case, and this arm completes it.

The solution in Rust

impl Solution {
    fn is_same_tree(p: &Option<Box<TreeNode>>, q: &Option<Box<TreeNode>>) -> bool {
        match (p, q) {
            (None, None) => true,
            (Some(p), Some(q)) => {
                if p.val != q.val {
                    return false;
                }
                Self::is_same_tree(&p.left, &q.left) && Self::is_same_tree(&p.right, &q.right)
            }
            _ => false,
        }
    }

    fn is_subtree(root: &Option<Box<TreeNode>>, sub_root: &Option<Box<TreeNode>>) -> bool {
        match root {
            None => false,
            Some(node) => {
                if Self::is_same_tree(root, sub_root) {
                    return true;
                }
                Self::is_subtree(&node.left, sub_root) || Self::is_subtree(&node.right, sub_root)
            }
        }
    }
}

Rust details worth a closer look:

Borrowing. Every parameter is a shared reference, so passing sub_root into each recursive call copies only the reference. A value passed without & would move into the first call and couldn't be used again.
Matching on a reference. match root has type &Option<Box<TreeNode>>, yet the patterns are written None and Some(node). Rust matches through the reference and gives node a borrow of the box, so nothing is moved out of the tree.
Shadowing. In (Some(p), Some(q)), the new p and q hide the parameters of the same names inside that arm. They refer to the nodes, which is why p.val compiles.
Tuple patterns. match (p, q) builds a pair of references and matches on both at once. The _ arm catches the two mixed cases, (Some, None) and (None, Some).
return only for the early exit. The final && and || expressions are the arms' values, so they have no semicolon and no return.

Complexity

Time: O(n · m). is_subtree visits each node of root at most once, and each visit calls is_same_tree, which looks at no more than m nodes because it stops as soon as sub_root runs out or a value differs.

Space: O(h), where h is the larger depth of the two trees, for the recursion stack. The lesson limits trees to 400 levels, which is safe for recursion.

Edge cases and common mistakes

Matching only the root. Checking is_same_tree(root, sub_root) once would miss a match deeper down. The recursive calls on both children are what try every node.
Same values, different shape. A subtree takes every descendant. With root = [3,4,5,1,2,None,None,None,None,0], node 4 matches [4,1,2] on its values, but the extra 0 below the 2 makes the trees different, so the result is false.
Forgetting the mixed case. When only one side is empty the trees differ. Without the _ => false arm the code wouldn't compile, and a wrong arm there would let a tree "match" a smaller one.
A tree is its own subtree. The root check happens before the recursion, so is_subtree(&t, &t) is true.
Single nodes. A leaf with value 5 against a leaf with value 5 gives true; against a leaf with value 6, false.
A bigger sub_root. A single node 1 against the tree 1 with a left child 2 gives false, because the comparison reaches a (None, Some) pair.
Mirror images. A tree with 2 on the right is not the same as one with 2 on the left, so 1 with right child 2 is not a subtree of 1 with left child 2. Left is compared with left only.

Testing

Running the reference solution on these trees prints:

root = [3,4,5,1,2], sub_root = [4,1,2] gives true.
root = [3,4,5,1,2,None,None,None,None,0], sub_root = [4,1,2] gives false.
root = [1,1], sub_root = [1] gives true.
root = [3,4,5,1,2] against itself gives true.
root = [1], sub_root = [1,2] gives false.
root = [5], sub_root = [6] gives false.
A chain of 400 nodes, each the left child of the next, all with value 1, against [2] gives false.

Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free