Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Thursday, June 4

    Subtree of another Tree

    Updated: Algorithms and Data Structures No Comments2 Mins Readdevangini123By

    Problem Statement:

    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.

    Examples:

    Example 1:

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

    Output: true

    Example 2:

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

    Output: false

    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].
    • -104 <= root.val <= 104
    • -104 <= subRoot.val <= 104

    Approach

    • Serialize both trees using preorder traversal (with null markers) into strings.
    • Check if subRoot's serialized string is a substring of root's serialized string.
    • If yes, subRoot is a subtree of root; return true, else false.

    Time Complexity:

  • Time Complexity = O(n * m)

    • Space Complexity:

  • Space Complexity = O(n + m) recursion stack space (h=tree height)

    • Dry Run

    Function Call: isSubtree(root, subRoot) where
    root = TreeNode(3)
    ├── left: TreeNode(4)
    │   ├── left: TreeNode(1)
    │   └── right: TreeNode(2)
    └── right: TreeNode(5)

    subRoot = TreeNode(4)
    ├── left: TreeNode(1)
    └── right: TreeNode(2)

    Step 1:
    → Call serialize(root)

    Serializing root:
    → curr = 3 → hash = “-3”
    → curr.left = 4 → hash = “-3-4”
    → curr.left.left = 1 → hash = “-3-4-1”
    → curr.left.left.left = null → hash = “-3-4-1-#”
    → curr.left.left.right = null → hash = “-3-4-1-#-#”
    → curr.left.right = 2 → hash = “-3-4-1-#-#-2”
    → curr.left.right.left = null → hash = “-3-4-1-#-#-2-#”
    → curr.left.right.right = null → hash = “-3-4-1-#-#-2-#-#”
    → curr.right = 5 → hash = “-3-4-1-#-#-2-#-#-5”
    → curr.right.left = null → hash = “-3-4-1-#-#-2-#-#-5-#”
    → curr.right.right = null → hash = “-3-4-1-#-#-2-#-#-5-#-#”

    Serialized root:
    → hashRoot = “-3-4-1-#-#-2-#-#-5-#-#”

    Step 2:
    → Call serialize(subRoot)

    Serializing subRoot:
    → curr = 4 → hash = “-4”
    → curr.left = 1 → hash = “-4-1”
    → curr.left.left = null → hash = “-4-1-#”
    → curr.left.right = null → hash = “-4-1-#-#”
    → curr.right = 2 → hash = “-4-1-#-#-2”
    → curr.right.left = null → hash = “-4-1-#-#-2-#”
    → curr.right.right = null → hash = “-4-1-#-#-2-#-#”

    Serialized subRoot:
    → hashSubRoot = “-4-1-#-#-2-#-#”

    Step 3:
    → Check if hashRoot includes hashSubRoot:
    → “-3-4-1-#-#-2-#-#-5-#-#” includes “-4-1-#-#-2-#-#” → true

    Final Result: true 
    
var isSubtree = function(root, subRoot) {
    let hashRoot = serialize(root);
    let hashSubRoot = serialize(subRoot);

    return hashRoot.includes(hashSubRoot);
};
let serialize = function(root) {
    let hash = "";
    let traversal = (curr) => {
        if(!curr) {
            hash = hash + "-#";
            return;
        }
        hash = hash + "-" + curr.val;
        traversal(curr.left);
        traversal(curr.right);
    }
    traversal(root);
    return hash;
}    
    
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def serialize(self, root):
        hash = []
        def dfs(node):
            if not node:
                hash.append("-#")
                return
            hash.append("-" + str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ''.join(hash)

    def isSubtree(self, root, subRoot):
        hashRoot = self.serialize(root)
        hashSubRoot = self.serialize(subRoot)
        return hashSubRoot in hashRoot
            
    
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class Solution {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }
    private void serializeHelper(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("-#");
            return;
        }
        sb.append("-").append(root.val);
        serializeHelper(root.left, sb);
        serializeHelper(root.right, sb);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        String hashRoot = serialize(root);
        String hashSubRoot = serialize(subRoot);
        return hashRoot.contains(hashSubRoot);
    }
}

     
    
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    string serialize(TreeNode* root) {
        string hash;
        serializeHelper(root, hash);
        return hash;
    }
    void serializeHelper(TreeNode* root, string& hash) {
        if (!root) {
            hash += "-#";
            return;
        }
        hash += "-" + to_string(root->val);
        serializeHelper(root->left, hash);
        serializeHelper(root->right, hash);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        string hashRoot = serialize(root);
        string hashSubRoot = serialize(subRoot);
        return hashRoot.find(hashSubRoot) != string::npos;
    }
};
    
    
// Pseudo-C style (illustrative only, not complete without memory management and tree setup)
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;
void serialize(TreeNode* root, char* buffer) {
    if (!root) {
        strcat(buffer, "-#");
        return;
    }
    char valStr[20];
    sprintf(valStr, "-%d", root->val);
    strcat(buffer, valStr);
    serialize(root->left, buffer);
    serialize(root->right, buffer);
}
int isSubtree(TreeNode* root, TreeNode* subRoot) {
    char hashRoot[1000] = "";
    char hashSubRoot[1000] = "";
    serialize(root, hashRoot);
    serialize(subRoot, hashSubRoot);
    return strstr(hashRoot, hashSubRoot) != NULL;
}
            
    
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public string Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        SerializeHelper(root, sb);
        return sb.ToString();
    }
    private void SerializeHelper(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.Append("-#");
            return;
        }
        sb.Append("-" + root.val);
        SerializeHelper(root.left, sb);
        SerializeHelper(root.right, sb);
    }
    public bool IsSubtree(TreeNode root, TreeNode subRoot) {
        string hashRoot = Serialize(root);
        string hashSubRoot = Serialize(subRoot);
        return hashRoot.Contains(hashSubRoot);
    }
}

    Keep Reading

    Add A Comment
    Leave A Reply

    Demo

    Courses

    Community

    Contact Us