Why are null markers required during serialization?

Without them, different binary-tree structures may produce the same traversal sequence. Null markers preserve missing-child positions and therefore preserve structure.

Can the root value of subRoot appear multiple times in the main tree?

Yes. Multiple nodes may contain the same value as the root of subRoot, but each candidate must still match the complete structure and values of subRoot.

What happens if a candidate subtree contains extra nodes?

It is not considered a valid match. When subRoot ends at a particular position, the candidate subtree must also end at the corresponding position.

Why is an exact comparison still performed after a hash match?

Different subtrees can theoretically produce the same hash because of a collision. An exact tree comparison after matching hashes ensures correctness.

Which approach is generally preferred in interviews?

The recursive compare-at-every-node solution is usually the simplest to explain and implement. Serialization with KMP provides a deterministic O(N + M) solution, while subtree hashing is useful when discussing optimized matching and hashing techniques.

Check If a Binary Tree Is a Subtree of Another Tree

Given the roots of two binary trees, root and subRoot, determine whether subRoot appears as a subtree of root.

A subtree must match an entire tree section starting from some node in root, including:

the same node values,
the same left-child structure,
the same right-child structure.

Return true if such a matching subtree exists. Otherwise, return false.

Example 1

Input:
root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]

Output:
true

Explanation:
The subtree rooted at node 4 in root has exactly the same values and structure as subRoot.

Example 2

Input:
root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]

Output:
false

Explanation:
Although a node with value 4 exists in root, its subtree contains an additional node 0. Therefore, its structure does not exactly match subRoot.

Practice it by yourself before moving onto the solutionTry now

Brute Force Approach

For subRoot to be a subtree of root, there must be some node in root from which the entire remaining tree structure is identical to subRoot.

Therefore, every node in root can be considered as a possible starting point.

Whenever a candidate node is considered, an identical-tree comparison is performed. For a valid match, both the node values and tree structure must match completely.

If the current candidate does not match, the search is continued through the left and right subtrees of root.

The main drawback is that the same portions of root may be compared repeatedly for different candidate nodes.

Algorithm

Every node of root is traversed because any node may represent the starting point of the required subtree.
For each candidate node, an identical-tree helper is called to compare the subtree rooted there with subRoot.
During comparison, a match is considered valid when both corresponding nodes are null.
A mismatch is reported when only one corresponding node is null or when their values differ.
If the current nodes match, their corresponding left subtrees and right subtrees are recursively compared.
true is returned as soon as a complete match is found; otherwise, the search is continued through the remaining nodes.
If no matching candidate is found, false is returned.

Dry Run

Subtree of Another Tree Brute Force Appraoch Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
5    int val;
6    TreeNode* left;
7    TreeNode* right;
8
9    TreeNode(int value) {
10        val = value;
11        left = nullptr;
12        right = nullptr;
13    }
14};
15
16class Solution {
17private:
18    // Checks whether two trees have
19    // exactly the same values and structure.
20    bool isSameTree(TreeNode* first, TreeNode* second) {
21        if (first == nullptr && second == nullptr) {
22            return true;
23        }
24
25        if (
26            first == nullptr ||
27            second == nullptr ||
28            first->val != second->val
29        ) {
30            return false;
31        }
32
33        return isSameTree(first->left, second->left) &&
34               isSameTree(first->right, second->right);
35    }
36
37public:
38    // Treats every node as a possible
39    // starting point of the required subtree.
40    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
41        if (subRoot == nullptr) {
42            return true;
43        }
44
45        if (root == nullptr) {
46            return false;
47        }
48
49        // A complete value-and-structure match
50        // confirms the required subtree.
51        if (isSameTree(root, subRoot)) {
52            return true;
53        }
54
55        return isSubtree(root->left, subRoot) ||
56               isSubtree(root->right, subRoot);
57    }
58};
59
60int main() {
61    TreeNode* root = new TreeNode(3);
62    root->left = new TreeNode(4);
63    root->right = new TreeNode(5);
64    root->left->left = new TreeNode(1);
65    root->left->right = new TreeNode(2);
66
67    TreeNode* subRoot = new TreeNode(4);
68    subRoot->left = new TreeNode(1);
69    subRoot->right = new TreeNode(2);
70
71    Solution solution;
72
73    cout << boolalpha
74         << solution.isSubtree(root, subRoot)
75         << endl;
76
77    return 0;
78}

Complexity Analysis

Let N be the number of nodes in root, M be the number of nodes in subRoot, H1 be the height of root, and H2 be the height of subRoot.

Time Complexity: O(N × M) in the worst case. Up to M nodes may be compared for many of the N possible candidate nodes in root.

Space Complexity: O(H1 + H2) in the worst case due to recursive calls used for searching root and comparing it with subRoot.

Better Approach

Two binary trees are identical only when both their values and structures are identical.

A tree can be represented using preorder traversal. However, storing only node values is insufficient because different structures can produce the same sequence.

For example:

    1            1
   /              \
  2                2

If missing children are ignored, both trees could produce:

1, 2

To preserve structure, special markers are included for null children.

For example, the two trees above would produce different serialized representations because the missing left and right positions are explicitly recorded.

Separators are also placed around values so that values such as 1 and 12 cannot accidentally produce partial matches.

Once both trees have been serialized, the problem becomes:

Does the serialized representation of subRoot occur inside the serialized representation of root?

KMP can be used to perform this pattern search in linear time.

Algorithm

Both root and subRoot are serialized using preorder traversal so that each node is recorded before its children.
Explicit null markers are inserted whenever missing children are encountered so that the complete tree structure is preserved.
Separators are included around node values so that one value cannot accidentally match part of another value.
The serialization of subRoot is treated as the pattern, while the serialization of root is treated as the text.
An LPS array is constructed for the pattern so that previously matched prefix information can be reused after a mismatch.
KMP pattern matching is performed to search for the complete serialized subRoot inside the serialized root.
true is returned if the entire pattern is found; otherwise, false is returned.

Dry Run

Subtree of Another Tree Better Appraoch Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Serializes values together with null markers
  // so both values and structure are preserved.
  void serialize(TreeNode* root, string& result) {
      if (root == nullptr) {
          result += "#,";
          return;
      }
25
      result += "^" + to_string(root->val) + ",";
27
      serialize(root->left, result);
      serialize(root->right, result);
  }
31
  // Builds the Longest Prefix Suffix array
  // used by KMP to reuse previous matches.
  vector<int> buildLps(const string& pattern) {
      vector<int> lps(pattern.size(), 0);
36
      int length = 0;
      int i = 1;
39
      while (i < pattern.size()) {
          if (pattern[i] == pattern[length]) {
              lps[i] = length + 1;
              length++;
              i++;
          } else if (length != 0) {
              // The next smaller prefix-suffix is reused
              // instead of restarting the comparison.
              length = lps[length - 1];
          } else {
              // No prefix-suffix match exists here,
              // so the next position must be examined.
              lps[i++] = 0;
          }
      }
55
      return lps;
  }
58
  // Searches for pattern inside text
  // using KMP pattern matching.
  bool kmpSearch(
      const string& text,
      const string& pattern
  ) {
      if (pattern.empty()) {
          return true;
      }
68
      vector<int> lps = buildLps(pattern);
70
      int i = 0;
      int j = 0;
73
      while (i < text.size()) {
          if (text[i] == pattern[j]) {
              i++;
              j++;
78
              if (j == pattern.size()) {
                  return true;
              }
          } else if (j != 0) {
              // The matched prefix is preserved by
              // falling back to its previous LPS length.
              j = lps[j - 1];
          } else {
              i++;
          }
      }
90
      return false;
  }
93
94public:
  bool isSubtree(TreeNode* root, TreeNode* subRoot) {
      if (subRoot == nullptr) {
          return true;
      }
99
      if (root == nullptr) {
          return false;
      }
103
      string rootSerialization;
      string subRootSerialization;
106
      serialize(root, rootSerialization);
      serialize(subRoot, subRootSerialization);
109
      return kmpSearch(
          rootSerialization,
          subRootSerialization
      );
  }
115};
116
117int main() {
  TreeNode* root = new TreeNode(3);
  root->left = new TreeNode(4);
  root->right = new TreeNode(5);

Complexity Analysis

Let N be the number of nodes in root and M be the number of nodes in subRoot.

Time Complexity: O(N + M). Both trees are serialized once, and KMP processes the resulting text and pattern in linear time. Since each node contributes only a constant number of serialization tokens, their lengths remain proportional to N and M.

Space Complexity: O(N + M). The serialized representations of both trees and the LPS array used by KMP require linear additional space.

Optimal Approach

Repeated identical-tree comparisons can be reduced by computing a compact signature for every subtree.

For each node, a hash is calculated using three pieces of information:

the current node's value,
the hash of its left subtree,
the hash of its right subtree.

Because both child hashes are included, the resulting signature depends on the subtree's values as well as its structure.

A fixed sentinel hash is assigned to null children so that missing children also contribute to the structure.

The hash of subRoot is computed first. A postorder traversal is then performed over root, allowing the left and right subtree hashes to be available before the current node's hash is calculated.

Whenever a subtree hash equals the hash of subRoot, that node is treated as a candidate. An exact identical-tree comparison is then performed only for such candidates so that correctness does not depend solely on hash equality.

The implementation may use constants such as:

the FNV offset basis as an initial hash seed;
0x9e3779b97f4a7c15ULL, a commonly used 64-bit golden-ratio-derived constant that helps mix hash components;
911382323ULL as a fixed non-zero sentinel hash for null children so that missing nodes affect the resulting subtree signature.

These constants do not change the algorithm itself; they are used to obtain better-distributed hash values and distinguish structural cases.

Algorithm

The hash of subRoot is computed using postorder traversal so that its complete value-and-structure signature is available before root is searched.
During hashing, a fixed sentinel value is assigned to every null child so that missing-child positions contribute to the subtree structure.
For every non-null node, its value, left-subtree hash, and right-subtree hash are combined using fixed mixing constants.
A postorder traversal of root is performed so that both child hashes are available before the current subtree hash is calculated.
Whenever the current subtree hash matches the hash of subRoot, an exact identical-tree comparison is performed to protect against possible hash collisions.
true is returned as soon as a hash-matching candidate is structurally verified.
If no verified candidate is found after the complete traversal, false is returned.

Dry Run

Subtree of Another Tree Optimal Appraoch Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Standard 64-bit FNV offset basis used
  // as the initial hash seed.
  static constexpr uint64_t FNV_OFFSET =
      14695981039346656037ULL;
22
  // Golden-ratio-derived constant helps
  // spread bits while combining hash values.
  static constexpr uint64_t MIX_CONSTANT =
      0x9e3779b97f4a7c15ULL;
27
  // Fixed non-zero sentinel makes null children
  // contribute to the subtree structure.
  static constexpr uint64_t NULL_HASH =
      911382323ULL;
32
  // Mixes one component into the
  // current 64-bit subtree hash.
  uint64_t combineHash(
      uint64_t hashValue,
      uint64_t value
  ) {
      hashValue ^=
          value +
          MIX_CONSTANT +
          (hashValue << 6) +
          (hashValue >> 2);
44
      return hashValue;
  }
47
  // Computes a hash that depends on the node value
  // and the structure of both child subtrees.
  uint64_t getHash(TreeNode* root) {
      if (root == nullptr) {
          return NULL_HASH;
      }
54
      uint64_t leftHash =
          getHash(root->left);
57
      uint64_t rightHash =
          getHash(root->right);
60
      uint64_t hashValue = FNV_OFFSET;
62
      hashValue = combineHash(
          hashValue,
          static_cast<uint64_t>(
              static_cast<int64_t>(root->val)
          )
      );
69
      hashValue =
          combineHash(hashValue, leftHash);
72
      hashValue =
          combineHash(hashValue, rightHash);
75
      return hashValue;
  }
78
  // Verifies a hash-matching candidate so
  // hash collisions cannot affect correctness.
  bool isSameTree(
      TreeNode* first,
      TreeNode* second
  ) {
      if (first == nullptr && second == nullptr) {
          return true;
      }
88
      if (
          first == nullptr ||
          second == nullptr ||
          first->val != second->val
      ) {
          return false;
      }
96
      return isSameTree(first->left, second->left) &&
             isSameTree(first->right, second->right);
  }
100
  // Computes subtree hashes in postorder and
  // checks only hash-matching candidates.
  uint64_t search(
      TreeNode* root,
      TreeNode* subRoot,
      uint64_t targetHash,
      bool& found
  ) {
      if (root == nullptr) {
          return NULL_HASH;
      }
112
      uint64_t leftHash =
          search(
              root->left,
              subRoot,
              targetHash,
              found
          );
120

Complexity Analysis

Let N be the number of nodes in root, M be the number of nodes in subRoot, H1 be the height of root, and H2 be the height of subRoot.

Time Complexity: O(N + M) on average. The hash of every subtree is computed once, and exact structural comparison is performed only when a candidate hash matches the hash of subRoot. In a pathological case with many hash collisions or many equal candidate signatures, verification can increase the worst-case time beyond this average bound.

Space Complexity: O(H1 + H2), where H1 and H2 represent the heights of root and subRoot, due to recursive traversal and verification calls. If subtree hashes are explicitly stored for every node instead of being propagated during recursion, additional O(N) space may be required.

Interview follow-up Questions

A subtree must contain the same values and the same structure. Two trees may contain identical values while arranging them differently between left and right children.

Check If a Binary Tree Is a Subtree of Another Tree

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Better Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Parent and Distance - Introduction

Flatten Binary Tree to Linked List

Count Nodes in a Complete Binary Tree

Check If a Binary Tree Is a Subtree of Another Tree

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Better Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Why is matching only node values not enough?

Why are null markers required during serialization?

Can the root value of subRoot appear multiple times in the main tree?

What happens if a candidate subtree contains extra nodes?

Why is an exact comparison still performed after a hash match?

Which approach is generally preferred in interviews?

Read Similar Blogs

Parent and Distance - Introduction

Flatten Binary Tree to Linked List

Count Nodes in a Complete Binary Tree