← Algorithmic Patterns
easyTrees

Subtree of Another Tree

Determine whether the second tree exactly matches a subtree rooted at some node of the first tree. An empty second tree is a subtree of every tree.

LeetCode ↗

Work through the cases

3 examples

Input notation

Two level-order trees on separate lines; null denotes missing nodes or an empty tree.

Expected result

true or false.
Case 1

Input

3 4 5 1 2
4 1 2

Expected output

true
Case 2

Input

3 4 5
4 1

Expected output

false
Case 3

Input

1
null

Expected output

true

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Ask whether subRoot equals some subtree of root. Comparing at every node is O(mn) in the worst case and fits the limits. same walks two trees together. The outer DFS invokes same at each node and returns on the first hit. Compare the root first so mismatches exit early.

We define a helper function same(p, q) to determine whether the tree rooted at p and the tree rooted at q are identical. If the root values of the two trees are equal, and their left and right subtrees are also respectively equal, then the two trees are identical.

In the isSubtree(root, subRoot) function, we first check if root is null. If it is, we return false. Otherwise, we check if root and subRoot are identical. If they are, we return true. Otherwise, we recursively check if the left or right subtree of root contains subRoot.

The time complexity is O(n × m), and the space complexity is O(n). Here, n and m are the number of nodes in the trees root and subRoot, respectively.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        return same(root, subRoot) || isSubtree(root.left, subRoot)
            || isSubtree(root.right, subRoot);
    }

    private boolean same(TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            return p == q;
        }
        return p.val == q.val && same(p.left, q.left) && same(p.right, q.right);
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.