Subtree of Another Tree - Practice Coding Problems

Subtree of Another Tree - Problem

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Input & Output

Example 1 — Basic Subtree Match

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

› Output: true

💡 Note: The subtree rooted at node 4 in the main tree has the exact same structure and values as subRoot: both have 4 as root with left child 1 and right child 2

Example 2 — No Match Found

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

› Output: false

💡 Note: Although node 4 exists in main tree, the subtree rooted at 4 has an additional node 0 under node 2, so it doesn't exactly match subRoot

Example 3 — Entire Tree Match

$ Input: root = [1,2,3], subRoot = [1,2,3]

› Output: true

💡 Note: The entire main tree matches the subRoot exactly - a tree is considered a subtree of itself

Constraints

The number of nodes in the root tree is in the range [1, 2000]
The number of nodes in the subRoot tree is in the range [1, 1000]
-10⁴ ≤ root.val ≤ 10⁴
-10⁴ ≤ subRoot.val ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Trees

Main tree [3,4,5,1,2] and target subtree [4,1,2]

Search Process

Check each node in main tree as potential subtree root

Match Found

Subtree rooted at node 4 matches target exactly

Key Takeaway

🎯 Key Insight: A subtree match requires identical structure AND node values at every corresponding position

Asked in

f Facebook 15 a Amazon 12 M Microsoft 8 G Google 6

The key insight is that a subtree must match exactly at every corresponding node. The brute force approach checks every node as a potential subtree root (O(m×n) time), while the string serialization approach converts trees to unique strings and uses substring matching (O(m+n) time, O(m+n) space).

Common Approaches

Approach	Time	Space	Notes
✓ String Serialization Approach	O(m + n)	O(m + n)	Convert trees to strings and use string matching
Brute Force DFS Comparison	O(m × n)	O(max(h₁, h₂))	Check every node in main tree as potential subtree root

String Serialization Approach — Algorithm Steps

Serialize main tree to string using preorder traversal
Serialize subtree to string using same method
Check if subtree string appears in main tree string

Visualization

Tap to expand

Step-by-Step Walkthrough

Serialize Main Tree

Convert main tree to string: #3,#4,#1,null,null,#2,null,null,#5,null,null

Serialize Subtree

Convert subtree to string: #4,#1,null,null,#2,null,null

String Match

Check if subtree string appears in main tree string

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

void serialize(struct TreeNode* node, char* result) {
    if (!node) {
        strcat(result, "null,");
        return;
    }
    char val_str[20];
    sprintf(val_str, "#%d,", node->val);
    strcat(result, val_str);
    serialize(node->left, result);
    serialize(node->right, result);
}

bool solution(struct TreeNode* root, struct TreeNode* subRoot) {
    char mainStr[10000] = "";
    char subStr[10000] = "";
    
    serialize(root, mainStr);
    serialize(subRoot, subStr);
    
    return strstr(mainStr, subStr) != NULL;
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode* buildTree(int* arr, int size) {
    if (size == 0) return NULL;
    
    struct TreeNode* root = createNode(arr[0]);
    struct TreeNode** queue = (struct TreeNode**)malloc(size * sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    queue[rear++] = root;
    int i = 1;
    
    while (front < rear && i < size) {
        struct TreeNode* node = queue[front++];
        
        if (i < size && arr[i] != -1001) {
            node->left = createNode(arr[i]);
            queue[rear++] = node->left;
        }
        i++;
        
        if (i < size && arr[i] != -1001) {
            node->right = createNode(arr[i]);
            queue[rear++] = node->right;
        }
        i++;
    }
    
    free(queue);
    return root;
}

int main() {
    int rootArr[1000], subRootArr[1000];
    int rootSize = 0, subRootSize = 0;
    
    // Simple parsing for demo
    rootArr[0] = 3; rootArr[1] = 4; rootArr[2] = 5; rootArr[3] = 1; rootArr[4] = 2;
    rootSize = 5;
    
    subRootArr[0] = 4; subRootArr[1] = 1; subRootArr[2] = 2;
    subRootSize = 3;
    
    struct TreeNode* root = buildTree(rootArr, rootSize);
    struct TreeNode* subRoot = buildTree(subRootArr, subRootSize);
    
    bool result = solution(root, subRoot);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m + n)

One traversal of main tree (m nodes) plus one traversal of subtree (n nodes)

✓ Linear Growth

Space Complexity

O(m + n)

String representations store all node values plus delimiters

⚡ Linearithmic Space

189.0K Views

Medium Frequency

~15 min Avg. Time

2.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

String Serialization Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler