Subtree of Another Tree

Easy
1875.

Subtree of Another Tree

Subtree of Another Tree is an easy coding problem on depth-first search, trees and string matching, asked in Amazon, Google, Microsoft and Meta interviews.

You are given the roots root and subRoot of two binary trees. Return true if root contains a subtree that is identical to subRoot — the same shape and the same values — and false otherwise.

A subtree of root is some node of root together with all of its descendants; root is a subtree of itself.

Example 1

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, matches `subRoot` exactly.

Example 2

Input
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output
false
Explanation
The node 4 has the right values on top, but its subtree also contains the 0 under 2 — a subtree must include every descendant.

Example 3

Input
root = [1,1], subRoot = [1]
Output
true
Explanation
The leaf 1 matches; the root 1 does not, because it has a child.

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]
  • -10^4 <= root.val <= 10^4
  • -10^4 <= subRoot.val <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} subRoot
 * @return {boolean}
 */
var isSubtree = function(root, subRoot) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Subtree of Another Tree — Solution in Python, Java & C++

Subtree of Another Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Subtree of Another Tree is an easy coding problem on depth-first search, trees and string matching, asked in Amazon, Google, Microsoft and Meta interviews.

Problem statement

You are given the roots root and subRoot of two binary trees. Return true if root contains a subtree that is identical to subRoot — the same shape and the same values — and false otherwise.

A subtree of root is some node of root together with all of its descendants; root is a subtree of itself.

Example 1

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, matches `subRoot` exactly.

Example 2

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Explanation: The node 4 has the right values on top, but its subtree also contains the 0 under 2 — a subtree must include every descendant.

Example 3

Input: root = [1,1], subRoot = [1]
Output: true
Explanation: The leaf 1 matches; the root 1 does not, because it has a child.

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]
  • -10^4 <= root.val <= 10^4
  • -10^4 <= subRoot.val <= 10^4

Hints for Subtree of Another Tree

  1. Hint 1

    Use the Same Tree check as a building block: is the tree rooted at this node identical to subRoot?

  2. Hint 2

    Try that check at every node of root — if any succeeds, the answer is true.

  3. Hint 3

    Matching tops are not enough: the comparison must fail when either side has a node the other lacks, all the way down to the leaves.

How to solve Subtree of Another Tree

subRoot occurs in root exactly when some node of root roots a tree identical to subRoot. Walk every node of root and run an identical-trees check from it.

Approach

  1. same(a, b): both null → true; one null → false; otherwise equal values and same on both child pairs.
  2. isSubtree(node, sub): if node is null return false.
  3. If same(node, sub) return true.
  4. Otherwise return isSubtree(node.left, sub) || isSubtree(node.right, sub).

Why it works

A subtree is determined by its top node, so trying every node of root as the top covers every candidate, and same accepts a candidate only if it matches subRoot node for node including where each one ends.

Complexity

  • Time — O(n · m) in the worst case, for n and m nodes; serialising both trees and string-matching brings it to O(n + m)
  • Space — O(h) recursion depth

Pitfalls

  • Checking only that subRoot's values appear starting at some node accepts a match with extra descendants (second example).
  • Serialising without null markers (or without separators between values) makes different trees look alike, e.g. 12 vs 1 2.

Reference solution

Python

from typing import Optional

def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    def same(a, b):
        if a is None or b is None:
            return a is b
        return a.val == b.val and same(a.left, b.left) and same(a.right, b.right)

    def walk(node):
        if node is None:
            return False
        return same(node, subRoot) or walk(node.left) or walk(node.right)

    return walk(root)

Java

public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) return false;
    return sameShape(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

static boolean sameShape(TreeNode a, TreeNode b) {
    if (a == null || b == null) return a == b;
    return a.val == b.val && sameShape(a.left, b.left) && sameShape(a.right, b.right);
}

C++

bool sameShape(TreeNode* a, TreeNode* b) {
    if (!a || !b) return a == b;
    return a->val == b->val && sameShape(a->left, b->left) && sameShape(a->right, b->right);
}

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    if (!root) return false;
    return sameShape(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

JavaScript

var isSubtree = function(root, subRoot) {
    if (root === null) return false;
    return sameShape(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};

var sameShape = function(a, b) {
    if (a === null || b === null) return a === b;
    return a.val === b.val && sameShape(a.left, b.left) && sameShape(a.right, b.right);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals