Solving Subtree of Another Tree in JavaScript: Step-by-Step Guide

Introduction to the Subtree of Another Tree Problem

The "Subtree of Another Tree" problem is a classic tree-based algorithm challenge frequently encountered in coding interviews and competitive programming. Given two binary trees — a root tree and a subRoot tree — the task is to determine whether the subRoot tree exists as an exact subtree within the root tree. A subtree is defined not just as any collection of nodes, but as a node and all of its descendants, meaning the structure and values must match exactly from that node downward.

This problem tests your understanding of tree traversal, recursion, and structural comparison. It is a foundational exercise that reinforces how to think about nested recursive structures, which appear everywhere from DOM manipulation to file system parsing.

Why This Problem Matters

Understanding how to solve the subtree problem builds essential skills for any JavaScript developer working with hierarchical data. Trees are the backbone of many real-world systems: the DOM is a tree, JSON structures are trees, organizational charts are trees, and abstract syntax trees (ASTs) power every JavaScript engine and bundler.

DOM manipulation: Checking whether a fragment of HTML exists within a larger document follows the same logic.
AST analysis: Linters and compilers frequently check whether a particular code pattern exists within a larger syntax tree.
Version control: Diffing algorithms rely on subtree comparisons to detect changes between file versions.
Interview readiness: This problem combines two fundamental techniques — tree traversal and tree equality — making it a favorite among interviewers at major tech companies.

Defining the Tree Structure

Before solving the problem, we need a clear representation of a binary tree node. In JavaScript, we typically define a tree node using a simple class with a value, a left child, and a right child.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

This structure allows us to build any binary tree by composing nodes. For example, we can construct a root tree and a candidate subtree as follows:

// Build the root tree:
//       3
//      / \
//     4   5
//    / \
//   1   2
const root = new TreeNode(
  3,
  new TreeNode(4, new TreeNode(1), new TreeNode(2)),
  new TreeNode(5)
);

// Build the subRoot tree:
//     4
//    / \
//   1   2
const subRoot = new TreeNode(4, new TreeNode(1), new TreeNode(2));

In this example, the subRoot tree matches the subtree rooted at node 4 in the root tree, so our function should return true.

Breaking Down the Approach

The solution can be divided into two distinct sub-problems. First, we need a helper function that checks whether two trees are identical — meaning every corresponding node has the same value and the same structure. Second, we need to traverse the root tree and, at each node, check whether the subtree starting at that node is identical to the subRoot tree.

Step 1: The Tree Equality Helper

The equality check is a straightforward recursive function. Two trees are identical if their root values are equal and both their left subtrees and right subtrees are identical. The base cases handle the scenarios where one or both nodes are null.

function isSameTree(p, q) {
  // Both nodes are null — trees match at this branch
  if (p === null && q === null) return true;

  // One node is null but the other is not — structure differs
  if (p === null || q === null) return false;

  // Values must match, and both subtrees must be identical
  return (
    p.val === q.val &&
    isSameTree(p.left, q.left) &&
    isSameTree(p.right, q.right)
  );
}

This helper runs in O(min(N, M)) time, where N and M are the sizes of the two trees being compared, because it stops as soon as it finds a mismatch.

Step 2: Traversing the Root Tree

With the equality helper in place, the main function traverses every node in the root tree. At each node, it checks whether the subtree rooted at that node is identical to the subRoot tree. If any check passes, we return true. If we exhaust all nodes without a match, we return false.

function isSubtree(root, subRoot) {
  // An empty subRoot is always a subtree
  if (subRoot === null) return true;

  // If root is null but subRoot is not, no match is possible
  if (root === null) return false;

  // Check if the tree starting at this node matches subRoot
  if (isSameTree(root, subRoot)) return true;

  // Otherwise, recurse into left and right children
  return (
    isSubtree(root.left, subRoot) ||
    isSubtree(root.right, subRoot)
  );
}

Putting It All Together

Now let us combine both functions into a complete, runnable example. We will build the trees, call the function, and log the result.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isSameTree(p, q) {
  if (p === null && q === null) return true;
  if (p === null || q === null) return false;
  return (
    p.val === q.val &&
    isSameTree(p.left, q.left) &&
    isSameTree(p.right, q.right)
  );
}

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

// Construct the root tree
const root = new TreeNode(
  3,
  new TreeNode(4, new TreeNode(1), new TreeNode(2)),
  new TreeNode(5)
);

// Construct the candidate subtree
const subRoot = new TreeNode(4, new TreeNode(1), new TreeNode(2));

console.log(isSubtree(root, subRoot)); // Output: true

When you run this code, the output is true because the subtree rooted at node 4 in the root tree exactly matches the subRoot tree in both structure and values.

Testing Edge Cases

A robust solution must handle edge cases gracefully. Let us examine several scenarios that often trip up developers.

// Edge case 1: subRoot is null — should return true
console.log(isSubtree(root, null)); // true

// Edge case 2: root is null, subRoot is not — should return false
console.log(isSubtree(null, subRoot)); // false

// Edge case 3: both are null — should return true
console.log(isSubtree(null, null)); // true

// Edge case 4: similar values but different structure
//       3
//      / \
//     4   5
//    / \
//   1   2
//      /
//     0
const rootWithExtra = new TreeNode(
  3,
  new TreeNode(
    4,
    new TreeNode(1),
    new TreeNode(2, new TreeNode(0))
  ),
  new TreeNode(5)
);

console.log(isSubtree(rootWithExtra, subRoot)); // false

The fourth edge case is particularly important. Even though the values 4, 1, and 2 appear in both trees, the structure differs because the root tree has an additional node 0 as the left child of node 2. This means the subtree rooted at node 4 is not identical to subRoot, and the function correctly returns false.

Analyzing Time and Space Complexity

Understanding the complexity of this solution is crucial for interviews and production code. Let us define N as the number of nodes in the root tree and M as the number of nodes in the subRoot tree.

Time complexity: In the worst case, we visit every node in the root tree, and at each node, we call isSameTree, which can take up to O(M) time. This gives us a worst-case time complexity of O(N × M). This worst case occurs when the trees share many similar values but differ only at the leaves, forcing many near-complete comparisons.

Space complexity: The space usage is dominated by the recursion stack. The depth of recursion for isSubtree is O(N) in the worst case of a skewed tree, and isSameTree adds up to O(M) depth. The overall space complexity is O(N + M) in the worst case, though for balanced trees it would be O(log N + log M).

Best Practices

Always handle null cases first: Null checks at the top of recursive functions prevent runtime errors and clarify the logic. Check both nodes for null before attempting to access their properties.
Separate concerns: Keep the equality check and the traversal logic in separate functions. This makes the code easier to read, test, and debug. Each function should have a single responsibility.
Use short-circuit evaluation: The || operator in the traversal step short-circuits as soon as one branch returns true, avoiding unnecessary recursive calls. Similarly, && in the equality check stops at the first mismatch.
Test with structural variations: Do not only test with matching values. Create test cases where values match but structures differ, where trees are skewed, and where the subtree appears deep in the tree.
Consider iterative alternatives for large trees: For very deep trees, recursion may cause stack overflow. In such cases, you can convert the recursive approaches to iterative ones using explicit stacks or queues.
Document your assumptions: Clarify whether the problem considers a tree to be a subtree of itself. In most definitions, it is, and the solution above naturally handles this because isSameTree(root, subRoot) will return true if they are identical.

Optimizing with Tree Serialization

For scenarios where you need to perform many subtree checks, there is an optimization using tree serialization. By converting both trees into string representations using a pre-order traversal with sentinel markers for null nodes, you can reduce the problem to a substring search.

function serialize(node) {
  if (node === null) return '#';
  return ',' + node.val + serialize(node.left) + serialize(node.right);
}

function isSubtreeSerialized(root, subRoot) {
  const rootStr = serialize(root);
  const subStr = serialize(subRoot);
  return rootStr.includes(subStr);
}

console.log(isSubtreeSerialized(root, subRoot)); // true

The leading commas and the # sentinel for null nodes are critical. Without them, a value like 12 could be falsely matched within a sequence representing 1 and 2 as separate nodes. This approach has a time complexity of O(N + M) for serialization plus the cost of the substring search, which can be O((N + M)²) in the worst case with naive string matching, or O(N + M) with advanced algorithms like KMP.

Conclusion

Solving the "Subtree of Another Tree" problem in JavaScript is a rewarding exercise that strengthens your grasp of recursion, tree traversal, and structural comparison. By breaking the problem into two clean sub-problems — an equality check and a traversal — you create a solution that is both readable and maintainable. The recursive approach covered here is the most intuitive starting point and performs well for typical interview and production scenarios. As your needs grow, optimizations like tree serialization can offer performance benefits for repeated queries. Mastering this problem equips you with patterns that transfer directly to more complex tree and graph challenges, making it a worthwhile addition to any JavaScript developer's toolkit.