Subtree of Another Tree

Easy · Trees · Explanation and code example

Depth First Search (DFS)

How it works

To check whether one tree is a subtree of another, we do two things:

  1. Walk through every node of the main tree (root) using DFS.
  2. At each node, check if the subtree starting here is exactly the same as subRoot.

So for every node in the big tree:

  • If its value matches subRoot's root, we compare both subtrees fully.
  • If they are identical, subRoot is a subtree.
  • Otherwise, continue searching on the left and right children.

The helper sameTree simply checks whether two trees match exactly, node-for-node.

Steps

  1. If subRoot is empty → return true (empty tree is always a subtree).
  2. If root is empty but subRoot is not → return false.
  3. At the current root node:
    • If sameTree(root, subRoot) is true, return true.
  4. Recursively check:
    • isSubtree(root.left, subRoot)
    • isSubtree(root.right, subRoot)
  5. Return true if either side returns true.

sameTree(root1, root2):

  1. If both nodes are null → return true.
  2. If only one is null → return false.
  3. If values differ → return false.
  4. Recursively check left children and right children.

Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m + n)

Where m is the number of nodes in subRoot and n is the number of nodes in root.

Things to watch for

Confusing Subtree with Substructure

A subtree must match exactly from a node down to all its leaves. A common mistake is checking only if the values match without verifying that the entire structure below also matches. If subRoot has children, those children must also exist and match in the main tree. Simply finding a node with the same value is not sufficient.

Incorrect Null Handling in Tree Comparison

When comparing two trees for equality, both trees must have null children in the same positions. A frequent error is returning true when one node is null and the other is not, or failing to check both left and right subtrees. The base case must ensure that both nodes being compared are either both null (return true) or both non-null with matching values before recursing.

Python code example

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot:
            return True
        if not root:
            return False

        if self.sameTree(root, subRoot):
            return True
        return (self.isSubtree(root.left, subRoot) or
               self.isSubtree(root.right, subRoot))

    def sameTree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root and not subRoot:
            return True
        if root and subRoot and root.val == subRoot.val:
            return (self.sameTree(root.left, subRoot.left) and
                   self.sameTree(root.right, subRoot.right))
        return False

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!subRoot) {
            return true;
        }
        if (!root) {
            return false;
        }

        if (sameTree(root, subRoot)) {
            return true;
        }
        return isSubtree(root->left, subRoot) ||
               isSubtree(root->right, subRoot);
    }

    bool sameTree(TreeNode* root, TreeNode* subRoot) {
        if (!root && !subRoot) {
            return true;
        }
        if (root && subRoot && root->val == subRoot->val) {
            return sameTree(root->left, subRoot->left) &&
                   sameTree(root->right, subRoot->right);
        }
        return false;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations