572. Subtree of Another Tree

EasyTreeDepth-First SearchBinary TreeString MatchingHash Function
Leetcode Link

Problem Description

In this problem, given two binary trees root and subRoot, we need to determine if the second tree, subRoot, is a subtree of the first tree root. In essence, we're checking if subRoot exists within root with the exact structure and node values. A binary tree's subtree includes any node and all its descendants, and this definition allows a binary tree to be a subtree of itself.

Flowchart Walkthrough

For the problem of checking if one tree is a subtree of another (as in Leetcode 572. Subtree of Another Tree), let's use the algorithm flowchart to determine the appropriate approach. Here's a step-by-step analysis based on the provided flowchart:

Is it a graph?

  • Yes: Although the data structure is specifically a tree, a tree is a type of graph.

Is it a tree?

  • Yes: The scenario explicitly involves trees (a subtree and the main tree).

Is the problem related to directed acyclic graphs (DAGs)?

  • No: The problem focuses specifically on trees and the subtree relation, which doesn't involve general directed acyclic graphs.

Is the problem related to shortest paths?

  • No: We are not finding shortest paths; we are checking for a match of a subtree within a larger tree.

Does the problem involve connectivity?

  • No: The concern here isn't about connectivity between different nodes in terms of graph theory, but about structural similarity and subtree matching.

Conclusion: Given it's a tree-related problem without focus on connectivity, path finding, or DAG-related computations — the flowchart prescribes the use of DFS for trees to explore and verify if one tree is a subtree of another. This involves traversing the tree depth-first to check for structural and data equality between the subtree and any candidate subtree in the larger tree.

Intuition

To solve this problem, we use a depth-first search (DFS) strategy. The logic revolves around a helper function dfs that compares two trees to see if they are identical. This is where the heavy lifting occurs, as we must compare each node of the two trees, verifying they have the same values and the same structure.

There are two core scenarios where the trees are deemed to be the same:

  1. Both trees are empty, which means that we've reached the end of both trees simultaneously, so they are identical up to this point.
  2. The current nodes of the trees are equal, and the left and right subtrees are also identical by recursion.

For other cases, if one node is None and the other isn't, or if the node values differ, we return False.

The main isSubtree function calls dfs with root and subRoot as parameters. If dfs returns True, then subRoot is indeed a subtree of root. If not, the function checks recursively if subRoot is a subtree of either the left or the right subtree of root. This ensures that we check all possible subtrees within root for a match with subRoot.

The search continues until:

  • We find a subtree that matches subRoot.
  • We exhaust all nodes in root without finding a matching subtree, in which case we conclude subRoot is not a subtree of root.

This solution is elegant and direct, leveraging recursion to compare subtrees of root with subRoot.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation of the provided solution follows the intuition of utilizing depth-first search (DFS). Here's a breakdown of the approach and implementation details:

  • A nested function dfs(root1, root2) is defined within the isSubtree method. The purpose of dfs is to compare two nodes from each tree and their respective subtrees for equality.

  • dfs uses recursion to navigate both trees simultaneously. If at any point the values of root1 and root2 do not match, or one is None and the other is not, False is returned, indicating the trees are not identical at those nodes.

  • In dfs, three conditions are evaluated for each pair of nodes:

    1. If both nodes are None, the subtrees are considered identical, and it returns True.
    2. If only one of the nodes is None, it means the structures differ, hence it returns False.
    3. If neither of the nodes is None, it checks whether the values are identical and proceeds to call dfs recursively on the left and right subtrees (dfs(root1.left, root2.left) and dfs(root1.right, root2.right)). If all these checks pass, True is returned.

  • In the main function isSubtree, which takes root and subRoot as arguments, we first ensure that root is not None. If root is None, there's no tree to search, so the function returns False.

  • The function recursively calls itself while also invoking dfs. It first calls dfs with root and subRoot to check for equality at the current nodes. If this does not yield a match, the function recursively checks the left and right subtrees of root with the calls self.isSubtree(root.left, subRoot) and self.isSubtree(root.right, subRoot) respectively.

  • Essentially, the solution method takes advantage of recursive tree traversal. First, it attempts to match the subRoot tree with the root using dfs and if unsuccessful, it moves onto root's left and right children, trying to find a match there, continuing the process until a match is found or all possibilities are exhausted.

The time complexity of the algorithm is O(n * m), with 'n' being the number of nodes in the root tree and 'm' being the number of nodes in the subRoot tree, considering the worst-case scenario where we need to check each node in root against subRoot.

The space complexity is O(n) due to the recursion, which could potentially go as deep as the height of the tree root in the worst-case scenario.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's imagine we have the following two binary trees:

Tree `root`:

      3
     / \
    4   5
   / \
  1   2

Tree `subRoot`:

    4
   / \
  1   2

We want to determine if subRoot is a subtree of root. According to the solution described above, we would perform the following steps:

  1. We call isSubtree with root (node with value 3) and subRoot (node with value 4).

  2. Inside isSubtree, we invoke dfs(root, subRoot):

    • It starts with comparing the root nodes of both trees. Since their values (3 and 4) do not match, dfs returns False.

  3. Since dfs did not find subRoot in the current root node, isSubtree now calls itself recursively to check if subRoot is a subtree of the left subtree of root.

    • We now repeat the process for root.left (node with value 4) and subRoot (node with value 4).
    • We call dfs(root.left, subRoot) and check the conditions:

      1. Both nodes are not None.

      2. Both nodes have the same value (4).

      3. We recursively call dfs on their left and right children:

        • For the left children of root.left (node with value 1) and subRoot (node with value 1), the values match, and they are both not None. The recursion on the left children calls dfs(root.left.left, subRoot.left) which would return True.

        • For the right children of root.left (node with value 2) and subRoot (node with value 2), the values also match, and they are both not None. The recursion on the right children calls dfs(root.left.right, subRoot.right) which would return True.

    • As all conditions for the dfs function are satisfied and both subcalls of dfs returned True, the dfs(root.left, subRoot) will return True.

  4. Since dfs(root.left, subRoot) returned True, isSubtree returns True. We conclude that subRoot is indeed a subtree of root, and our search is complete.

Using the defined algorithm, we managed to determine that subRoot is a subtree of root effectively through recursive depth-first search. Each step of recursion allowed us to compare corresponding nodes and their children, validating that subRoot not only shares the same values but also the exact structure and node placement within root.

Solution Implementation

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def is_subtree(self, root: TreeNode, sub_root: TreeNode) -> bool:
9        # Helper function that checks if two trees are identical
10        def is_same_tree(tree1, tree2):
11            # If both trees are empty, they are identical
12            if tree1 is None and tree2 is None:
13                return True
14            # If one tree is empty and the other is not, they are not identical
15            if tree1 is None or tree2 is None:
16                return False
17            # Check if the current nodes have the same value 
18            # and recursively check left and right subtrees
19            return (tree1.val == tree2.val and
20                    is_same_tree(tree1.left, tree2.left) and
21                    is_same_tree(tree1.right, tree2.right))
22
23        # If the main tree is empty, sub_root cannot be a subtree of it
24        if root is None:
25            return False
26        # Check if the current trees are identical, or if the sub_root is a subtree 
27        # of the left subtree or right subtree of the current root
28        return (is_same_tree(root, sub_root) or
29                self.is_subtree(root.left, sub_root) or
30                self.is_subtree(root.right, sub_root))
31
32# Note: Do not modify the method names such as `is_subtree` as per the instructions.
33
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8
9    TreeNode() {}
10  
11    TreeNode(int val) {
12        this.val = val;
13    }
14  
15    TreeNode(int val, TreeNode left, TreeNode right) {
16        this.val = val;
17        this.left = left;
18        this.right = right;
19    }
20}
21
22class Solution {
23    /**
24     * Determines if a binary tree has a subtree that matches a given subtree.
25     *
26     * @param root The root node of the main tree.
27     * @param subRoot The root node of the subtree that we are looking for in the main tree.
28     * @return boolean indicating if the subtree is present in the main tree.
29     */
30    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
31        // If the main tree is null, subRoot cannot be a subtree
32        if (root == null) {
33            return false;
34        }
35        // Check if the tree rooted at this node is identical to the subRoot
36        // or if the subRoot is a subtree of the left or right child
37        return isIdentical(root, subRoot) || isSubtree(root.left, subRoot)
38            || isSubtree(root.right, subRoot);
39    }
40
41    /**
42     * Helper method to determine if two binary trees are identical.
43     *
44     * @param root1 The root node of the first tree.
45     * @param root2 The root node of the second tree.
46     * @return boolean indicating whether the trees are identical or not.
47     */
48    private boolean isIdentical(TreeNode root1, TreeNode root2) {
49        // If both trees are empty, then they are identical
50        if (root1 == null && root2 == null) {
51            return true;
52        }
53        // If both are not null, compare their values and check their left & right subtrees
54        if (root1 != null && root2 != null) {
55            return root1.val == root2.val && isIdentical(root1.left, root2.left)
56                && isIdentical(root1.right, root2.right);
57        }
58        // If one is null and the other isn't, they are not identical
59        return false;
60    }
61}
62
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    // Function to check if a given subtree `subRoot` is a subtree of the main tree `root`
16    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
17        // If the main tree root is null, then `subRoot` cannot be a subtree
18        if (!root) return false;
19      
20        // Check if trees are identical or if `subRoot` is a subtree of either left or right subtrees
21        return isIdentical(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
22    }
23
24    // Helper function to check if two trees are identical
25    bool isIdentical(TreeNode* treeOne, TreeNode* treeTwo) {
26        // If both trees are empty, they are identical
27        if (!treeOne && !treeTwo) return true;
28        // If one of the trees is empty, they are not identical
29        if (!treeOne || !treeTwo) return false;
30      
31        // Compare the values and recursively check left and right subtrees
32        return treeOne->val == treeTwo->val &&
33               isIdentical(treeOne->left, treeTwo->left) &&
34               isIdentical(treeOne->right, treeTwo->right);
35    }
36};
37
1/**
2 * Definition for a binary tree node.
3 */
4interface TreeNode {
5  val: number;
6  left: TreeNode | null;
7  right: TreeNode | null;
8}
9
10/**
11 * Performs a deep-first-search to check if the two given trees
12 * are identical.
13 * @param {TreeNode | null} root The node of the first tree.
14 * @param {TreeNode | null} subRoot The node of the second tree (subtree candidate).
15 * @return {boolean} True if both trees are identical, otherwise false.
16 */
17const isIdentical = (root: TreeNode | null, subRoot: TreeNode | null): boolean => {
18  // If both nodes are null, they are identical by definition.
19  if (!root && !subRoot) {
20    return true;
21  }
22
23  // If one of the nodes is null or values do not match, trees aren't identical.
24  if (!root || !subRoot || root.val !== subRoot.val) {
25    return false;
26  }
27
28  // Check recursively if the left subtree and right subtree are identical.
29  return isIdentical(root.left, subRoot.left) && isIdentical(root.right, subRoot.right);
30};
31
32/**
33 * Checks if one tree is subtree of another tree.
34 * @param {TreeNode | null} root The root of the main tree.
35 * @param {TreeNode | null} subRoot The root of the subtree.
36 * @return {boolean} True if the second tree is a subtree of the first tree, otherwise false.
37 */
38function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
39  // If the main tree is null, there can't be a subtree.
40  if (!root) {
41    return false;
42  }
43
44  // If the current subtrees are identical, return true.
45  // Otherwise, continue the search in the left or right subtree of the main tree.
46  return isIdentical(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
47}
48

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(m*n), where m is the number of nodes in the root tree and n is the number of nodes in the subRoot tree. For each node of the root, we perform a depth-first search (DFS) comparison with the subRoot, which is O(n) for each call. Since the DFS might be called for each node in the root, this results in O(m*n) in the worst case.

Space Complexity

The space complexity of the given code is O(max(h1, h2)), where h1 is the height of the root tree and h2 is the height of the subRoot tree. This is due to the space required for the call stack during the execution of the depth-first search. Since the recursion goes as deep as the height of the tree, the maximum height of the trees dictates the maximum call stack size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More