Skip to content

Volume ITechnology

4.14.6 — Subtree of Another Tree ​

LeetCode 572 · Easy · ★ Blind 75

The problem ​

You are given the roots of two binary trees, root and subRoot. Return true if subRoot appears inside root as a subtree. A subtree of root is one node of root together with everything below it. You cannot take a node and only part of what hangs below it.

root:      3          subRoot:   4
         /   \                  / \       →  true
        4     5                1   2
       / \
      1   2

root:      3          subRoot:   4
         /   \                  / \       →  false
        4     5                1   2
       / \                            (node 4 in root has an extra 0
      1   2                            under the 2, so its subtree is
         /                             not the same as subRoot)
        0

root has up to 2,000 nodes, and subRoot has up to 1,000.

What the problem is really asking ​

Two smaller questions, and you already know how to answer the first.

  1. Starting from a given node of root, is the tree there exactly the same as subRoot? That is 4.14.5 Same Tree.
  2. Is there any node of root where the answer to question 1 is yes? That means trying every node of root as a starting point.

The brute force ​

The plan above is already the straightforward approach. It is also the expected first answer. A faster method exists, and it comes after.

The solution ​

python
class Solution:
    def isSubtree(self, root, subRoot) -> bool:
        if not subRoot:                                   # (1)
            return True
        if not root:                                      # (2)
            return False

        if self.isSame(root, subRoot):                    # (3)
            return True

        return (self.isSubtree(root.left, subRoot)        # (4)
                or self.isSubtree(root.right, subRoot))

    def isSame(self, p, q) -> bool:                       # (5)
        if not p and not q:
            return True
        if not p or not q:
            return False
        return (p.val == q.val
                and self.isSame(p.left, q.left)
                and self.isSame(p.right, q.right))
ts
function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  if (!subRoot) return true;                              // (1)
  if (!root) return false;                                // (2)
  if (isSame(root, subRoot)) return true;                 // (3)
  return isSubtree(root.left, subRoot)                    // (4)
      || isSubtree(root.right, subRoot);
}

function isSame(p: TreeNode | null, q: TreeNode | null): boolean {   // (5)
  if (!p && !q) return true;
  if (!p || !q) return false;
  return p.val === q.val && isSame(p.left, q.left) && isSame(p.right, q.right);
}

Line by line ​

(1) An empty subRoot is a subtree of anything. By convention, the empty tree sits under every missing child. The real problem never passes an empty subRoot, but the line keeps the function well defined. In an interview, ask what they want here, because it is genuinely a choice.

(2) We ran out of root without a match. There is nothing left to try.

(3) Try this node as the starting point. If the tree starting here is exactly subRoot, we are done.

(4) Otherwise, try the left side, then the right side. or stops at the first True, so once a match is found on the left, the right side is never searched.

(5) The Same Tree check from 4.14.5, unchanged.

Keep these as two separate functions, each with one job. isSubtree searches for a starting point. isSame checks one starting point. Trying to do both in a single function is where people get tangled, because "same tree from here" and "anywhere below here" need different base cases.

Trace ​

Take the first example. subRoot is 4 with children 1 and 2.

isSubtree called onisSame with subRoot?Next
33 ≠ 4 → notry left child 4
44 = 4, then (1, 1) same, then (2, 2) same → yesreturn true

The right child 5 is never visited.

In the second example, isSame(4, subRoot) reaches the pair (2, 2). Node 2 in root has a left child 0, but node 2 in subRoot has none. That is the "one missing" case, so it returns false. The search then tries 1, 2, 0 and 5 as starting points, finds no match, and returns false.

Complexity, derived ​

Let n be the size of root and m the size of subRoot.

Time. isSubtree visits each of the n nodes. At each one, isSame may compare up to m pairs. So the worst case is O(n \cdot m).

In practice it is usually much faster, because most comparisons fail at the very first node, when the values differ. The bad case is a tree where every node holds the same value. Then every comparison runs deep before failing.

Space. The recursion is as deep as the taller of the two trees, so O(h).

A faster way: turn the trees into strings ​

There is a genuinely faster approach, and the idea carries over to many other problems. Write each tree out as a string, then ask whether one string contains the other.

From 4.14.5 you know a careless string does not pin down a tree's shape. So the string needs two things.

  1. A marker for every missing child, written #. Without it, two different shapes can give the same string.
  2. A separator before every value. Without it, a value of 2 could be found inside a value of 12.
python
def isSubtree(self, root, subRoot) -> bool:
    def serialise(node) -> str:
        if not node:
            return "#"                                       # a missing child
        return f",{node.val},{serialise(node.left)}{serialise(node.right)}"

    return serialise(subRoot) in serialise(root)             # substring search

The comma written before each value is what stops ,2, from matching inside ,12,.

Python's in on strings is fast in practice. To guarantee linear time, you would use the KMP string-search algorithm, which finds a pattern of length m in a text of length n in O(n + m) time, even in the worst case. It is explained in 4.31. That makes the whole solution O(n + m).

Give the simple version first. Then offer this one, and say what makes it correct: the missing-child markers and the separators. That detail is the real content.

Edge cases ​

  • subRoot equals the whole of root. Line (3) matches at the very first node.
  • subRoot is a single leaf. Any leaf in root with the same value matches.
  • A matching value with extra nodes below, like the second example. isSame catches the extra node.
  • Many equal values. Correct, but this is the slow case for the simple version.

Variations you will meet ​

  • Find Duplicate Subtrees. Turn every subtree into a string and count the strings in a hash map. Any string seen twice is a duplicate. It is the fingerprint idea from 4.4.4 Group Anagrams, applied to trees.
  • Comparing big trees by fingerprint. Give each subtree a short fingerprint built from its children's fingerprints. Then two huge trees can be compared by comparing just their top fingerprints. Version-control tools like Git compare folders of files this way.

The general lesson: turning a tree into a string, carefully enough that the string pins down the tree, turns tree problems into string problems.

What the interviewer will push on ​

"Why is the worst case O(n \cdot m), and when does it happen?" A tree of repeated values, where comparisons run deep before failing.

"Can you do better?" Turn both trees into strings and search for one inside the other, with KMP for a guaranteed O(n + m).

"Why do you need the markers and the commas?" Without markers, the string does not pin down the shape. Without separators, 2 matches inside 12.

"Does an empty subRoot count as a subtree?" Usually yes. Ask, because it is a genuine choice.

One thing to volunteer: keep the search and the comparison as two functions, and say why. It shows you think about what each piece of recursion means.

Next: 4.14.7 Lowest Common Ancestor of a BST. The first problem that uses a search tree's ordering, not just its shape.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet