Start learning free

LESSON 419 OF 540 · BINARY TREES

Subtree of Another Tree in Kotlin: O(n · m) 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 null 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,null,null,null,null,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 -104 and 104.
  • 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 8
    Ctrl + Enter to check

    KOTLIN · BINARY TREES

    Subtree Of Another Tree in Kotlin, explained

    Problem overview

    You get two binary trees, root and subRoot. The function isSubtree returns true when some node of root, taken together with all of its descendants, forms exactly the tree subRoot: the same shape and the same value in every position. A tree counts as a subtree of itself.

    The lesson provides the TreeNode class, with an Int property value and two nullable children, left and right. An empty child is null.

    Take root = [3,4,5,1,2] and subRoot = [4,1,2]. The node 4 in root has the children 1 and 2 and nothing below them, which is exactly subRoot, so the answer is true. Now give the 2 a child 0: root = [3,4,5,1,2,null,null,null,null,0]. The node 4 still looks right from the top, but its subtree is bigger than subRoot, and no other node fits, so the answer is false. Matching the top of the tree is not enough: everything below must match too.

    Approach

    Split the question in two:

    1. Given a node of root, is the tree that starts there identical to subRoot?
    2. Which nodes of root should we try?

    The second question has a simple answer: all of them. If subRoot starts at the top of root, we are done. Otherwise it must be a subtree of the left child's tree or of the right child's tree, which is the same question on a smaller tree. That is a recursion over root.

    The first question is also a recursion, over two trees at once. Two trees are identical when both are empty, or when both are non-empty, their root values are equal, their left subtrees are identical and their right subtrees are identical. That is a helper function, isSameTree.

    The brute force here is already the intended solution: no cleverness is needed, only two small recursions that cooperate.

    Step by step

    The outer search, isSubtree

    1. Stop at an empty tree. If root is null, return false. subRoot has at least one node, and an empty tree has no node where it could start. This is also what ends the recursion when it steps below a leaf.
    2. Try the current node. If isSameTree(root, subRoot) is true, return true at once.
    3. Try lower down. Otherwise return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot). The || operator skips the right call if the left one already found a match.

    The comparison, isSameTree

    1. Both empty. If p and q are both null, the trees are identical: return true. This is the stopping case when both sides run past a leaf together.
    2. Only one empty. Both empty was handled above, so if either is null here, exactly one is. The shapes differ: return false.
    3. Different values. Both nodes exist now, so compare p.value with q.value and return false if they differ.
    4. Recurse. The roots match, so the trees are identical exactly when the left pair and the right pair are: isSameTree(p.left, q.left) && isSameTree(p.right, q.right).

    The solution in Kotlin

    class Solution {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        if (p == null && q == null) {
            return true
        }
        if (p == null || q == null) {
            return false
        }
        if (p.value != q.value) {
            return false
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }

    fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
        if (root == null) {
            return false
        }
        if (isSameTree(root, subRoot)) {
            return true
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
    }
}

    Kotlin details worth knowing

    • Nullable parameters and smart casts. The parameters have the type TreeNode?, so Kotlin won't let you read p.value until it knows p isn't null. After if (p == null || q == null) { return false } it knows that both are non-null, so p.value and q.value compile with no !! and no ?.. Without that check you get: only safe (?.) or non-null asserted (!!.) calls are allowed on a nullable receiver of type 'TreeNode?'. The same happens in isSubtree: after the root == null check, root.left is allowed.
    • Parameters are read-only. A function parameter can't be reassigned, which is why the smart cast is reliable here.
    • == against null. In Kotlin, p == null is the normal null test; it's safe even for a nullable p.
    • && and || short-circuit. The right-hand side runs only when needed, which saves work but doesn't change the result.
    • The order of the checks matters. The "both null" test must come before the "either null" test. Swap them and two empty trees would be reported as different.

    Complexity

    Let n be the number of nodes in root and m the number in subRoot.

    • Time: O(n · m). isSubtree visits each of the n nodes of root at most once and starts one comparison at each. A comparison walks both trees in step and stops at the first difference, and it can never go past the m nodes of subRoot (when subRoot is exhausted, a bigger tree below gives a mismatch). So each comparison costs at most O(m).
    • Space: O(h) for the recursion stack, where h is the larger of the two trees' heights. The constraints keep trees at most 400 levels deep, so the recursion stays shallow enough.

    Edge cases and common mistakes

    • Checking only the root values. Comparing the value at the top and stopping gives wrong answers. In the second example, node 4's children match, but the extra node 0 below the 2 makes the trees different. The comparison must go all the way down, and the empty children must match too.
    • Forgetting that a subtree includes every descendant. Matching a few levels of root and ignoring what hangs below is the same bug in another form.
    • Same value repeated. With root = [1,1] and subRoot = [1], the top node fails the comparison (it has a child) but its left child passes. Don't give up when the first candidate fails: the search has to continue below.
    • The tree itself. subRoot equal to root gives true, because the first comparison at the top already succeeds.
    • Treating null children as irrelevant. A missing child is part of the shape. A node with one child is different from a node with none.

    Testing

    Trees are written in level order, with null for a missing child. These inputs and results come from running the solution above:

    rootsubRootResult
    [3,4,5,1,2][4,1,2]true
    [3,4,5,1,2,null,null,null,null,0][4,1,2]false
    [1,1][1]true
    [1,2,3][1,2,3]true
    [1][2]false
    [1,null,1,null,1,null,1][1,null,1]true
    [3,4,5,1,2][4,1]false

    The last row is a good one to think about: node 4 has children 1 and 2, while subRoot has only the child 1, so the shapes differ.

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