Check if a Binary Tree is subtree of another Binary Tree

Last Updated : 6 Apr, 2026

Given two binary trees, a tree T (root1) with n nodes and a tree S (root2) with m nodes, check whether S is a subtree of T. A tree S is a subtree of T if it is formed by choosing any node in T and including all of its descendants. If S exactly matches any such subtree of T in both structure and node values, then it is considered a subtree.

Examples:

Input:

Output: true
Explanation: root2 is the subtree of root1.

Try it on GfG Practice

Table of Content

[Naive Approach] Preorder Traversal with Subtree Matching - O(n*m) Time and O(n+m) Space
[Better Approach] Using String Serialisation & Substring Matching - O(n*m) Time and O(n+m) Space
[Expected Approach] Using String Serialisation & KMP algorithm - O(n+m) Time and O(n+m) Space

[Naive Approach] Preorder Traversal with Subtree Matching - O(n*m) Time and O(n+m) Space

Traverse the main tree (root1) in preorder. At each node, treat it as a potential root and check whether the subtree rooted at this node is identical to root2. The identical check is done by recursively comparing both trees for matching structure and node values. Return true if a match is found at any node, otherwise, continue the traversal.

C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = right = nullptr;
    }
};

// Check if two trees are identical
bool areIdentical(Node* root1, Node* root2) {

    // Both nodes are null → identical
    if (root1 == nullptr && root2 == nullptr)
        return true;

    // One is null => not identical
    if (root1 == nullptr || root2 == nullptr)
        return false;

    // Check current node and recurse on children
    return (root1->data == root2->data &&
            areIdentical(root1->left, root2->left) &&
            areIdentical(root1->right, root2->right));
}

bool isSubTree(Node* root1, Node* root2) {

    // Empty subtree => always true
    if (root2 == nullptr)
        return true;

    // Main tree empty but subtree not => false
    if (root1 == nullptr)
        return false;

    // Match found at current node
    if (areIdentical(root1, root2))
        return true;

    // Otherwise, search in left and right
    return isSubTree(root1->left, root2) ||
           isSubTree(root1->right, root2);
}

int main() {

    // Construct Tree root1
    //          26
    //         /  \
    //        10   3
    //       / \    \
    //      4   6    3
    //       \
    //        30
    Node* root1 = new Node(26);
    root1->left = new Node(10);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(6);
    root1->left->left->right = new Node(30);
    root1->right->right = new Node(3);

    // Construct Tree root2
    //          10
    //         /  \
    //        4    6
    //         \
    //          30
    Node* root2 = new Node(10);
    root2->left = new Node(4);
    root2->right = new Node(6);
    root2->left->right = new Node(30);

    cout << (isSubTree(root1, root2) ? "true" : "false");

    return 0;
}

Java

class Node {
    int data;
    Node left;
    Node right;

    Node(int value) {
        data = value;
        left = right = null;
    }
}

class GFG {

    // Check if two trees are identical
    static boolean areIdentical(Node root1, Node root2) {

        // Both nodes are null → identical
        if (root1 == null && root2 == null)
            return true;

        // One is null → not identical
        if (root1 == null || root2 == null)
            return false;

        // Check current node and recurse on children
        return (root1.data == root2.data &&
                areIdentical(root1.left, root2.left) &&
                areIdentical(root1.right, root2.right));
    }

    static boolean isSubTree(Node root1, Node root2) {

        // Empty subtree → always true
        if (root2 == null)
            return true;

        // Main tree empty but subtree not → false
        if (root1 == null)
            return false;

        // Match found at current node
        if (areIdentical(root1, root2))
            return true;

        // Otherwise, search in left and right
        return isSubTree(root1.left, root2) ||
               isSubTree(root1.right, root2);
    }

    public static void main(String[] args) {

        // Construct Tree root1
        //          26
        //         /  \
        //        10   3
        //       / \    \
        //      4   6    3
        //       \
        //        30
        Node root1 = new Node(26);
        root1.left = new Node(10);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(6);
        root1.left.left.right = new Node(30);
        root1.right.right = new Node(3);

        // Construct Tree root2
        //          10
        //         /  \
        //        4    6
        //         \
        //          30
        Node root2 = new Node(10);
        root2.left = new Node(4);
        root2.right = new Node(6);
        root2.left.right = new Node(30);

        System.out.println(isSubTree(root1, root2) ? "true" : "false");
    }
}

Python

class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None

# Check if two trees are identical
def areIdentical(root1, root2):

    # Both nodes are null → identical
    if root1 is None and root2 is None:
        return True

    # One is null → not identical
    if root1 is None or root2 is None:
        return False

    # Check current node and recurse on children
    return (root1.data == root2.data and
            areIdentical(root1.left, root2.left) and
            areIdentical(root1.right, root2.right))

def isSubTree(root1, root2):

    # Empty subtree → always true
    if root2 is None:
        return True

    # Main tree empty but subtree not → false
    if root1 is None:
        return False

    # Match found at current node
    if areIdentical(root1, root2):
        return True

    # Otherwise, search in left and right
    return (isSubTree(root1.left, root2) or
            isSubTree(root1.right, root2))


if __name__ == "__main__":

    # Construct Tree root1
    #          26
    #         /  \
    #        10   3
    #       / \    \
    #      4   6    3
    #       \
    #        30
    root1 = Node(26)
    root1.left = Node(10)
    root1.right = Node(3)
    root1.left.left = Node(4)
    root1.left.right = Node(6)
    root1.left.left.right = Node(30)
    root1.right.right = Node(3)

    # Construct Tree root2
    #          10
    #         /  \
    #        4    6
    #         \
    #          30
    root2 = Node(10)
    root2.left = Node(4)
    root2.right = Node(6)
    root2.left.right = Node(30)

    print("true" if isSubTree(root1, root2) else "false")

C#

using System;

class Node {
    public int data;
    public Node left;
    public Node right;

    public Node(int value) {
        data = value;
        left = right = null;
    }
}

class GFG {

    // Check if two trees are identical
    static bool AreIdentical(Node root1, Node root2) {

        // Both nodes are null → identical
        if (root1 == null && root2 == null)
            return true;

        // One is null → not identical
        if (root1 == null || root2 == null)
            return false;

        // Check current node and recurse on children
        return (root1.data == root2.data &&
                AreIdentical(root1.left, root2.left) &&
                AreIdentical(root1.right, root2.right));
    }

    static bool isSubTree(Node root1, Node root2) {

        // Empty subtree → always true
        if (root2 == null)
            return true;

        // Main tree empty but subtree not → false
        if (root1 == null)
            return false;

        // Match found at current node
        if (AreIdentical(root1, root2))
            return true;

        // Otherwise, search in left and right
        return isSubTree(root1.left, root2) ||
               isSubTree(root1.right, root2);
    }

    static void Main() {

        // Construct Tree root1
        //          26
        //         /  \
        //        10   3
        //       / \    \
        //      4   6    3
        //       \
        //        30
        Node root1 = new Node(26);
        root1.left = new Node(10);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(6);
        root1.left.left.right = new Node(30);
        root1.right.right = new Node(3);

        // Construct Tree root2
        //          10
        //         /  \
        //        4    6
        //         \
        //          30
        Node root2 = new Node(10);
        root2.left = new Node(4);
        root2.right = new Node(6);
        root2.left.right = new Node(30);

        Console.WriteLine(isSubTree(root1, root2) ? "true" : "false");
    }
}

JavaScript

class Node {
    constructor(value) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}

// Check if two trees are identical
function areIdentical(root1, root2) {

    // Both nodes are null → identical
    if (root1 === null && root2 === null)
        return true;

    // One is null → not identical
    if (root1 === null || root2 === null)
        return false;

    // Check current node and recurse on children
    return (root1.data === root2.data &&
            areIdentical(root1.left, root2.left) &&
            areIdentical(root1.right, root2.right));
}


function isSubTree(root1, root2) {

    // Empty subtree → always true
    if (root2 === null)
        return true;

    // Main tree empty but subtree not → false
    if (root1 === null)
        return false;

    // Match found at current node
    if (areIdentical(root1, root2))
        return true;

    // Otherwise, search in left and right
    return isSubTree(root1.left, root2) ||
           isSubTree(root1.right, root2);
}


// Driver Code

// Construct Tree root1
//          26
//         /  \
//        10   3
//       / \    \
//      4   6    3
//       \
//        30
const root1 = new Node(26);
root1.left = new Node(10);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.left.right = new Node(6);
root1.left.left.right = new Node(30);
root1.right.right = new Node(3);

// Construct Tree root2
//          10
//         /  \
//        4    6
//         \
//          30
const root2 = new Node(10);
root2.left = new Node(4);
root2.right = new Node(6);
root2.left.right = new Node(30);

console.log(isSubTree(root1, root2) ? "true" : "false");

Output

true

[Better Approach] Using String Serialisation & Substring Matching - O(n*m) Time and O(n+m) Space

Convert both trees into strings using preorder traversal, and include a special marker (like #) for every null node to preserve the exact structure of the tree. This ensures that different tree structures do not produce the same serialised string. Once both trees are serialised, check if the serialised string of root2 is a substring of the serialised string of root1. If it is found, then root2 is a subtree of root1.

Why this works?

Preorder traversal visits nodes in root => left => right order, so the relative position of each node is preserved in the serialised string.
Adding null markers (#) for missing children and a separator (,) for values ensure that the exact structure of the tree is captured along with the node values.
Because both node values and structure are recorded, each tree gets a unique serialised representation.
This prevents false matches, since two different trees cannot produce the same serialised string.
After serialisation, the subtree check reduces to a simple substring search between the two strings.
While serializing a binary tree with n nodes using preorder traversal, we include a null marker (#) for every null child.
A binary tree with n nodes has exactly (n+1) null child => (n+1) null markers. So, the serialized string contains n node values and (n + 1) null markers.
Total number of items = n + (n+1) = 2n + 1. We add separator (,) also to ensure that concatenation of two node values is not treated as a third value in the string. So total items become (2n + 1) + (2n for separators). Hence, space required = O(4n + 1) ≈ O(n).

C++

#include <iostream>
#include <string>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = right = nullptr;
    }
};

// Serialize tree using preorder with null markers
void serialize(Node* root, string &s) {

    // Null node → add marker
    if (root == nullptr) {
        s += "# ";
        return;
    }

    // Add current node
    s += to_string(root->data) + " ";

    // Recurse on left and right
    serialize(root->left, s);
    serialize(root->right, s);
}

bool isSubTree(Node* root1, Node* root2) {

    string s1 = "", s2 = "";

    // Serialize both trees
    serialize(root1, s1);
    serialize(root2, s2);

    // Check substring
    return (s1.find(s2) != string::npos);
}


int main() {

    // Construct Tree root1
    //          26
    //         /  \
    //        10   3
    //       / \    \
    //      4   6    3
    //       \
    //        30
    Node* root1 = new Node(26);
    root1->left = new Node(10);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(6);
    root1->left->left->right = new Node(30);
    root1->right->right = new Node(3);

    // Construct Tree root2
    //          10
    //         /  \
    //        4    6
    //         \
    //          30
    Node* root2 = new Node(10);
    root2->left = new Node(4);
    root2->right = new Node(6);
    root2->left->right = new Node(30);

    if (isSubTree(root1, root2))
        cout << "true";
    else
        cout << "false";

    return 0;
}

Java

import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int value) {
        data = value;
        left = right = null;
    }
}

class GFG {

    // Serialize tree using preorder with null markers
    static void serialize(Node root, StringBuilder s) {

        // Null node → add marker
        if (root == null) {
            s.append("# ");
            return;
        }

        // Add current node
        s.append(root.data).append(" ");

        // Recurse on left and right
        serialize(root.left, s);
        serialize(root.right, s);
    }

    static boolean isSubTree(Node root1, Node root2) {

        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();

        // Serialize both trees
        serialize(root1, s1);
        serialize(root2, s2);

        // Check substring
        return s1.toString().contains(s2.toString());
    }

    public static void main(String[] args) {

        // Construct Tree root1
        //          26
        //         /  \
        //        10   3
        //       / \    \
        //      4   6    3
        //       \
        //        30
        Node root1 = new Node(26);
        root1.left = new Node(10);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(6);
        root1.left.left.right = new Node(30);
        root1.right.right = new Node(3);

        // Construct Tree root2
        //          10
        //         /  \
        //        4    6
        //         \
        //          30
        Node root2 = new Node(10);
        root2.left = new Node(4);
        root2.right = new Node(6);
        root2.left.right = new Node(30);

        if (isSubTree(root1, root2))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

Python

class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None


# Serialize tree using preorder with null markers
def serialize(root, s):

    # Null node → add marker
    if root is None:
        s.append("# ")
        return

    # Add current node
    s.append(str(root.data) + " ")

    # Recurse on left and right
    serialize(root.left, s)
    serialize(root.right, s)


def isSubTree(root1, root2):

    s1 = []
    s2 = []

    # Serialize both trees
    serialize(root1, s1)
    serialize(root2, s2)

    # Convert to string
    str1 = "".join(s1)
    str2 = "".join(s2)

    # Check substring
    return str2 in str1



if __name__ == "__main__":

    # Construct Tree root1
    #          26
    #         /  \
    #        10   3
    #       / \    \
    #      4   6    3
    #       \
    #        30
    root1 = Node(26)
    root1.left = Node(10)
    root1.right = Node(3)
    root1.left.left = Node(4)
    root1.left.right = Node(6)
    root1.left.left.right = Node(30)
    root1.right.right = Node(3)

    # Construct Tree root2
    #          10
    #         /  \
    #        4    6
    #         \
    #          30
    root2 = Node(10)
    root2.left = Node(4)
    root2.right = Node(6)
    root2.left.right = Node(30)

    print("true" if isSubTree(root1, root2) else "false")

C#

using System;
using System.Text;

class Node {
    public int data;
    public Node left, right;

    public Node(int value) {
        data = value;
        left = right = null;
    }
}

class GFG {

    // Serialize tree using preorder with null markers
    static void serialize(Node root, StringBuilder s) {

        // Null node → add marker
        if (root == null) {
            s.Append("# ");
            return;
        }

        // Add current node
        s.Append(root.data + " ");

        // Recurse on left and right
        serialize(root.left, s);
        serialize(root.right, s);
    }


    static bool isSubTree(Node root1, Node root2) {

        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();

        // Serialize both trees
        serialize(root1, s1);
        serialize(root2, s2);

        // Check substring
        return s1.ToString().Contains(s2.ToString());
    }

    static void Main() {

        // Construct Tree root1
        //          26
        //         /  \
        //        10   3
        //       / \    \
        //      4   6    3
        //       \
        //        30
        Node root1 = new Node(26);
        root1.left = new Node(10);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(6);
        root1.left.left.right = new Node(30);
        root1.right.right = new Node(3);

        // Construct Tree root2
        //          10
        //         /  \
        //        4    6
        //         \
        //          30
        Node root2 = new Node(10);
        root2.left = new Node(4);
        root2.right = new Node(6);
        root2.left.right = new Node(30);

        Console.WriteLine(isSubTree(root1, root2) ? "true" : "false");
    }
}

JavaScript

class Node {
    constructor(value) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}

// Serialize tree using preorder with null markers
function serialize(root, arr) {

    // Null node → add marker
    if (root === null) {
        arr.push("# ");
        return;
    }

    // Add current node
    arr.push(root.data + " ");

    // Recurse on left and right
    serialize(root.left, arr);
    serialize(root.right, arr);
}

// Check if root2 is a subtree of root1
function isSubTree(root1, root2) {

    let s1 = [];
    let s2 = [];

    // Serialize both trees
    serialize(root1, s1);
    serialize(root2, s2);

    // Convert to string
    let str1 = s1.join("");
    let str2 = s2.join("");

    // Check substring
    return str1.includes(str2);
}


// Driver Code

// Construct Tree root1
//          26
//         /  \
//        10   3
//       / \    \
//      4   6    3
//       \
//        30
let root1 = new Node(26);
root1.left = new Node(10);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.left.right = new Node(6);
root1.left.left.right = new Node(30);
root1.right.right = new Node(3);

// Construct Tree root2
//          10
//         /  \
//        4    6
//         \
//          30
let root2 = new Node(10);
root2.left = new Node(4);
root2.right = new Node(6);
root2.left.right = new Node(30);

console.log(isSubTree(root1, root2) ? "true" : "false");

Output

true

[Expected Approach] Using String Serialisation & KMP algorithm - O(n+m) Time and O(n+m) Space

This is mainly an optimization over the above approach. The idea is to use KMP algorithm for substring check to ensure that we have overall linear time complexity. Similar to this approach another methods can also be used for substring matching like Boyer–Moore and Trie-based matching.

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = right = nullptr;
    }
};

// Serialize tree using preorder with null markers
void serialize(Node* root, string &s) {

    // Null node => add marker
    if (root == nullptr) {
        s += "# ";
        return;
    }

    // Add current node
    s += to_string(root->data) + " ";

    // Recurse on left and right
    serialize(root->left, s);
    serialize(root->right, s);
}

// Build LPS array for KMP
vector<int> buildLPS(string &pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);

    int len = 0, i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            lps[i++] = ++len;
        } else {
            if (len != 0)
                len = lps[len - 1];
            else
                i++;
        }
    }

    return lps;
}

// KMP search: check if pattern exists in text
bool kmpSearch(string &text, string &pattern) {
    vector<int> lps = buildLPS(pattern);

    int i = 0, j = 0;

    while (i < text.length()) {

        // Characters match => move both
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }

        // Full pattern matched
        if (j == pattern.length())
            return true;

        // Mismatch after some matches
        else if (i < text.length() && text[i] != pattern[j]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }

    return false;
}


bool isSubTree(Node* root1, Node* root2) {

    // Serialize both trees
    string s1 = "", s2 = "";
    serialize(root1, s1);
    serialize(root2, s2);

    // Apply KMP to check substring
    return kmpSearch(s1, s2);
}

int main() {

    // Construct Tree root1
    //          26
    //         /  \
    //        10   3
    //       / \    \
    //      4   6    3
    //       \
    //        30
    Node* root1 = new Node(26);
    root1->left = new Node(10);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(6);
    root1->left->left->right = new Node(30);
    root1->right->right = new Node(3);

    // Construct Tree root2
    //          10
    //         /  \
    //        4    6
    //         \
    //          30
    Node* root2 = new Node(10);
    root2->left = new Node(4);
    root2->right = new Node(6);
    root2->left->right = new Node(30);

    cout << (isSubTree(root1, root2) ? "true" : "false");

    return 0;
}

Java

import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int value) {
        data = value;
        left = right = null;
    }
}

class GFG {

    // Serialize tree using preorder with null markers
    void serialize(Node root, StringBuilder s) {

        // Null node => add marker
        if (root == null) {
            s.append("# ");
            return;
        }

        // Add current node
        s.append(root.data).append(" ");

        // Recurse on left and right
        serialize(root.left, s);
        serialize(root.right, s);
    }

    // Build LPS array for KMP
    int[] buildLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];

        int len = 0, i = 1;

        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                lps[i++] = ++len;
            } else {
                if (len != 0)
                    len = lps[len - 1];
                else
                    i++;
            }
        }

        return lps;
    }

    // KMP search
    boolean kmpSearch(String text, String pattern) {
        int[] lps = buildLPS(pattern);

        int i = 0, j = 0;

        while (i < text.length()) {

            // Match => move both
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            }

            // Full match found
            if (j == pattern.length())
                return true;

            // Mismatch after match
            else if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i++;
            }
        }

        return false;
    }


    boolean isSubTree(Node root1, Node root2) {

        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();

        // Serialize both trees
        serialize(root1, s1);
        serialize(root2, s2);

        // Apply KMP
        return kmpSearch(s1.toString(), s2.toString());
    }

    public static void main(String[] args) {

        // Construct Tree root1
        //          26
        //         /  \
        //        10   3
        //       / \    \
        //      4   6    3
        //       \
        //        30
        Node root1 = new Node(26);
        root1.left = new Node(10);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(6);
        root1.left.left.right = new Node(30);
        root1.right.right = new Node(3);

        // Construct Tree root2
        //          10
        //         /  \
        //        4    6
        //         \
        //          30
        Node root2 = new Node(10);
        root2.left = new Node(4);
        root2.right = new Node(6);
        root2.left.right = new Node(30);

        GFG obj = new GFG();
        System.out.println(obj.isSubTree(root1, root2) ? "true" : "false");
    }
}

Python

class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None


# Serialize tree using preorder with null markers
def serialize(root, s):

    # Null node => add marker
    if root is None:
        s.append("#")
        return

    # Add current node
    s.append(str(root.data))

    # Recurse on left and right
    serialize(root.left, s)
    serialize(root.right, s)


# Build LPS array for KMP
def buildLPS(pattern):
    lps = [0] * len(pattern)

    length = 0
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                i += 1

    return lps


# KMP search
def kmpSearch(text, pattern):
    lps = buildLPS(pattern)

    i = j = 0

    while i < len(text):

        # Match => move both
        if text[i] == pattern[j]:
            i += 1
            j += 1

        # Full match found
        if j == len(pattern):
            return True

        # Mismatch after match
        elif i < len(text) and text[i] != pattern[j]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return False


def isSubTree(root1, root2):

    s1 = []
    s2 = []

    # Serialize both trees
    serialize(root1, s1)
    serialize(root2, s2)

    # Convert to string
    str1 = " ".join(s1)
    str2 = " ".join(s2)

    # Apply KMP
    return kmpSearch(str1, str2)


if __name__ == "__main__":

    # Construct Tree root1
    #          26
    #         /  \
    #        10   3
    #       / \    \
    #      4   6    3
    #       \
    #        30
    root1 = Node(26)
    root1.left = Node(10)
    root1.right = Node(3)
    root1.left.left = Node(4)
    root1.left.right = Node(6)
    root1.left.left.right = Node(30)
    root1.right.right = Node(3)

    # Construct Tree root2
    #          10
    #         /  \
    #        4    6
    #         \
    #          30
    root2 = Node(10)
    root2.left = Node(4)
    root2.right = Node(6)
    root2.left.right = Node(30)

    print("true" if isSubTree(root1, root2) else "false")

C#

using System;
using System.Text;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;

    public Node(int value) {
        data = value;
        left = right = null;
    }
}

class GFG {

    // Serialize tree using preorder with null markers
    static void serialize(Node root, StringBuilder s) {

        // Null node => add marker
        if (root == null) {
            s.Append("# ");
            return;
        }

        // Add current node
        s.Append(root.data + " ");

        // Recurse on left and right
        serialize(root.left, s);
        serialize(root.right, s);
    }

    // Build LPS array for KMP
    static int[] buildLPS(string pattern) {
        int m = pattern.Length;
        int[] lps = new int[m];

        int len = 0, i = 1;

        while (i < m) {
            if (pattern[i] == pattern[len]) {
                lps[i++] = ++len;
            } else {
                if (len != 0)
                    len = lps[len - 1];
                else
                    i++;
            }
        }

        return lps;
    }

    // KMP search
    static bool kmpSearch(string text, string pattern) {
        int[] lps = buildLPS(pattern);

        int i = 0, j = 0;

        while (i < text.Length) {

            // Match => move both
            if (text[i] == pattern[j]) {
                i++;
                j++;
            }

            // Full match found
            if (j == pattern.Length)
                return true;

            // Mismatch after match
            else if (i < text.Length && text[i] != pattern[j]) {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i++;
            }
        }

        return false;
    }

    // Check if root2 is a subtree of root1
    static bool isSubTree(Node root1, Node root2) {

        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();

        // Serialize both trees
        serialize(root1, s1);
        serialize(root2, s2);

        // Apply KMP
        return kmpSearch(s1.ToString(), s2.ToString());
    }

    static void Main() {

        // Construct Tree root1
        //          26
        //         /  \
        //        10   3
        //       / \    \
        //      4   6    3
        //       \
        //        30
        Node root1 = new Node(26);
        root1.left = new Node(10);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(6);
        root1.left.left.right = new Node(30);
        root1.right.right = new Node(3);

        // Construct Tree root2
        //          10
        //         /  \
        //        4    6
        //         \
        //          30
        Node root2 = new Node(10);
        root2.left = new Node(4);
        root2.right = new Node(6);
        root2.left.right = new Node(30);

        Console.WriteLine(isSubTree(root1, root2) ? "true" : "false");
    }
}

JavaScript

class Node {
    constructor(value) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}

// Serialize tree using preorder with null markers
function serialize(root, arr) {

    // Null node => add marker
    if (root === null) {
        arr.push("# ");
        return;
    }

    // Add current node
    arr.push(root.data + " ");

    // Recurse on left and right
    serialize(root.left, arr);
    serialize(root.right, arr);
}

// Build LPS array for KMP
function buildLPS(pattern) {
    const lps = new Array(pattern.length).fill(0);

    let len = 0, i = 1;

    while (i < pattern.length) {
        if (pattern[i] === pattern[len]) {
            lps[i++] = ++len;
        } else {
            if (len !== 0)
                len = lps[len - 1];
            else
                i++;
        }
    }

    return lps;
}

// KMP search
function kmpSearch(text, pattern) {
    const lps = buildLPS(pattern);

    let i = 0, j = 0;

    while (i < text.length) {

        // Match => move both
        if (text[i] === pattern[j]) {
            i++;
            j++;
        }

        // Full match found
        if (j === pattern.length)
            return true;

        // Mismatch after match
        else if (i < text.length && text[i] !== pattern[j]) {
            if (j !== 0)
                j = lps[j - 1];
            else
                i++;
        }
    }

    return false;
}


function isSubTree(root1, root2) {

    let s1 = [];
    let s2 = [];

    // Serialize both trees
    serialize(root1, s1);
    serialize(root2, s2);

    // Convert to string
    let str1 = s1.join("");
    let str2 = s2.join("");

    // Apply KMP
    return kmpSearch(str1, str2);
}


// Driver Code

// Construct Tree root1
//          26
//         /  \
//        10   3
//       / \    \
//      4   6    3
//       \
//        30
let root1 = new Node(26);
root1.left = new Node(10);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.left.right = new Node(6);
root1.left.left.right = new Node(30);
root1.right.right = new Node(3);

// Construct Tree root2
//          10
//         /  \
//        4    6
//         \
//          30
let root2 = new Node(10);
root2.left = new Node(4);
root2.right = new Node(6);
root2.left.right = new Node(30);

console.log(isSubTree(root1, root2) ? "true" : "false");

Output

true

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem