Jobs

Interviews

Discussions

Subtree of Another Tree

Easy

Asked by:

11 views

Topics:

TreesRecursion

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.

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].
-10⁴ <= root.val <= 10⁴
-10⁴ <= subRoot.val <= 10⁴

Subtree of Another Tree

Easy

Asked by:

11 views

Topics:

TreesRecursion

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.

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].
-10⁴ <= root.val <= 10⁴
-10⁴ <= subRoot.val <= 10⁴

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the node values be negative or zero?
Are the trees balanced or can they be highly unbalanced?
Is an empty tree considered a subtree of any tree, including another empty tree?
If 'root' and 'subRoot' are identical, should I return true?
What is the maximum number of nodes in 'root' and 'subRoot' trees?

Brute Force Solution

Approach

We want to see if one tree is contained within another. The brute force way is to check every possible place where the smaller tree *could* be inside the larger one, one by one. We are meticulously exploring every single possibility.

Here's how the algorithm would work step-by-step:

Start at the very top of the bigger tree.
See if the smaller tree exactly matches the bigger tree, starting from the top.
If they match perfectly, great! We're done.
If not, move to the next spot in the bigger tree – either the left branch or the right branch.
Now, again, see if the smaller tree exactly matches the bigger tree, starting from this new spot.
Keep doing this - moving to different spots within the bigger tree and checking for a match - until you've looked at every single possible starting point in the bigger tree.
If you find a match at any of those spots, then the smaller tree is indeed a subtree of the bigger tree.

Code Implementation

def is_subtree(root_of_larger_tree, root_of_smaller_tree):

    if not root_of_smaller_tree:
        return True
    if not root_of_larger_tree:
        return False

    def are_identical(node_one, node_two):
        if not node_one and not node_two:
            return True
        if not node_one or not node_two or node_one.val != node_two.val:
            return False
        return are_identical(node_one.left, node_two.left) and are_identical(node_one.right, node_two.right)

    # If trees are identical, return True immediately
    if are_identical(root_of_larger_tree, root_of_smaller_tree):
        return True

    # Check left subtree
    if is_subtree(root_of_larger_tree.left, root_of_smaller_tree):
        return True

    # Check right subtree, if left subtree returned False
    if is_subtree(root_of_larger_tree.right, root_of_smaller_tree):
        return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm traverses the larger tree of size 'm' in the worst-case scenario to potentially visit each node. At each node in the larger tree, it compares the subtree rooted at that node with the smaller tree of size 'n'. The comparison operation (checking if two trees are identical) takes O(n) time in the worst case. Therefore, the overall time complexity is O(m*n), where 'm' is the number of nodes in the larger tree and 'n' is the number of nodes in the smaller tree.

Space Complexity

O(H) – The algorithm's space complexity is primarily determined by the depth of the recursion stack. The `isSubtree` function calls `isSameTree` which recursively traverses the tree. In the worst-case scenario, the recursion depth is equal to the height of the bigger tree. Therefore, the space complexity is O(H), where H is the height of the bigger tree. In the worst case, the tree might be skewed (like a linked list) where H is N (the number of nodes).

Optimal Solution

Approach

To efficiently check if one tree is a subtree of another, we'll explore the larger tree and compare its nodes. We'll look for nodes in the larger tree that have the same value as the root of the smaller tree, and then perform a more detailed comparison from that point.

Here's how the algorithm would work step-by-step:

Start by looking at the root node of the bigger tree.
Check if the value of the current node in the bigger tree is the same as the value of the root node of the smaller tree.
If the values are the same, then perform a check to see if the subtree starting at the current node of the bigger tree is exactly the same structure and has the same values as the smaller tree.
If the trees are exactly the same, you've found a subtree and can stop. Return true.
If the values are not the same or if the subtrees did not match, move to the left child of the current node of the bigger tree and repeat the process, checking values and comparing subtrees.
If you've checked the left child and still haven't found a match, do the same thing for the right child.
If you have looked at every node in the bigger tree and have not found a matching subtree, then return false, indicating that it is not a subtree.

Code Implementation

def is_subtree(root_tree, sub_tree):
    if not sub_tree:
        return True
    if not root_tree:
        return False

    def is_identical(node_one, node_two):
        if not node_one and not node_two:
            return True
        if not node_one or not node_two or node_one.val != node_two.val:
            return False
        return is_identical(node_one.left, node_two.left) and \
               is_identical(node_one.right, node_two.right)

    def traverse_tree(root_node, sub_node):
        # Check for identical subtree at current node
        if is_identical(root_node, sub_node):
            return True

        # Recursively search left and right subtrees
        if root_node.left and traverse_tree(root_node.left, sub_node):
            return True
        if root_node.right and traverse_tree(root_node.right, sub_node):
            return True

        return False

    # Initiate the recursive traversal to find the subtree
    return traverse_tree(root_tree, sub_tree)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – The outer function traverses each node in the larger tree (size m) in the worst case. For each node in the larger tree, the `isSameTree` function is called, which, in the worst case, traverses the entire smaller tree (size n) to determine if the subtree rooted at that node is identical to the smaller tree. Therefore, in the worst-case scenario where we must check every node in the larger tree, the time complexity becomes approximately m * n, which simplifies to O(m*n).

Space Complexity

O(H) – The space complexity is primarily determined by the recursion depth of the `isSubtree` function and the `isSameTree` helper function. In the worst-case scenario, the recursion depth for `isSubtree` can be the height (H) of the larger tree (s). The `isSameTree` function also contributes to the recursion depth, but its depth is limited by the height of the smaller tree (t), which is at most H if t is indeed a subtree of s. Therefore, the maximum space required for the call stack is proportional to the height H of the larger tree. Thus the space complexity is O(H), where H is the height of the larger tree.

Edge Cases

Case	How to Handle
root is null and subRoot is null	Return true, as an empty tree is considered a subtree of itself.
root is not null, but subRoot is null	Return true, as an empty tree is considered a subtree of any non-empty tree.
root is null, but subRoot is not null	Return false, as a non-empty tree cannot be a subtree of an empty tree.
root and subRoot are single nodes with equal values	Return true, as they are identical trees.
root and subRoot are single nodes with different values	Return false, as they are not identical trees.
Large trees with deep recursion depth (potential stack overflow)	Consider iterative approaches using a stack to avoid stack overflow errors or optimize recursive calls.
root and subRoot have identical structures but very large integer values in the nodes (potential overflow during comparisons)	Use a language feature that supports large integers (e.g., Python's arbitrary precision integers) or a hash of the tree structure to avoid comparisons of large numbers directly.
root contains many identical subtrees that could potentially match subRoot, but only one actually does	The algorithm should ensure that it correctly identifies the valid subtree and doesn't terminate prematurely on a false positive.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the node values be negative or zero?
Are the trees balanced or can they be highly unbalanced?
Is an empty tree considered a subtree of any tree, including another empty tree?
If 'root' and 'subRoot' are identical, should I return true?
What is the maximum number of nodes in 'root' and 'subRoot' trees?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the bigger tree.
See if the smaller tree exactly matches the bigger tree, starting from the top.
If they match perfectly, great! We're done.
If not, move to the next spot in the bigger tree – either the left branch or the right branch.
Now, again, see if the smaller tree exactly matches the bigger tree, starting from this new spot.
Keep doing this - moving to different spots within the bigger tree and checking for a match - until you've looked at every single possible starting point in the bigger tree.
If you find a match at any of those spots, then the smaller tree is indeed a subtree of the bigger tree.

Code Implementation

def is_subtree(root_of_larger_tree, root_of_smaller_tree):

    if not root_of_smaller_tree:
        return True
    if not root_of_larger_tree:
        return False

    def are_identical(node_one, node_two):
        if not node_one and not node_two:
            return True
        if not node_one or not node_two or node_one.val != node_two.val:
            return False
        return are_identical(node_one.left, node_two.left) and are_identical(node_one.right, node_two.right)

    # If trees are identical, return True immediately
    if are_identical(root_of_larger_tree, root_of_smaller_tree):
        return True

    # Check left subtree
    if is_subtree(root_of_larger_tree.left, root_of_smaller_tree):
        return True

    # Check right subtree, if left subtree returned False
    if is_subtree(root_of_larger_tree.right, root_of_smaller_tree):
        return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the root node of the bigger tree.
Check if the value of the current node in the bigger tree is the same as the value of the root node of the smaller tree.
If the values are the same, then perform a check to see if the subtree starting at the current node of the bigger tree is exactly the same structure and has the same values as the smaller tree.
If the trees are exactly the same, you've found a subtree and can stop. Return true.
If the values are not the same or if the subtrees did not match, move to the left child of the current node of the bigger tree and repeat the process, checking values and comparing subtrees.
If you've checked the left child and still haven't found a match, do the same thing for the right child.
If you have looked at every node in the bigger tree and have not found a matching subtree, then return false, indicating that it is not a subtree.

Code Implementation

def is_subtree(root_tree, sub_tree):
    if not sub_tree:
        return True
    if not root_tree:
        return False

    def is_identical(node_one, node_two):
        if not node_one and not node_two:
            return True
        if not node_one or not node_two or node_one.val != node_two.val:
            return False
        return is_identical(node_one.left, node_two.left) and \
               is_identical(node_one.right, node_two.right)

    def traverse_tree(root_node, sub_node):
        # Check for identical subtree at current node
        if is_identical(root_node, sub_node):
            return True

        # Recursively search left and right subtrees
        if root_node.left and traverse_tree(root_node.left, sub_node):
            return True
        if root_node.right and traverse_tree(root_node.right, sub_node):
            return True

        return False

    # Initiate the recursive traversal to find the subtree
    return traverse_tree(root_tree, sub_tree)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
root is null and subRoot is null	Return true, as an empty tree is considered a subtree of itself.
root is not null, but subRoot is null	Return true, as an empty tree is considered a subtree of any non-empty tree.
root is null, but subRoot is not null	Return false, as a non-empty tree cannot be a subtree of an empty tree.
root and subRoot are single nodes with equal values	Return true, as they are identical trees.
root and subRoot are single nodes with different values	Return false, as they are not identical trees.
Large trees with deep recursion depth (potential stack overflow)	Consider iterative approaches using a stack to avoid stack overflow errors or optimize recursive calls.
root and subRoot have identical structures but very large integer values in the nodes (potential overflow during comparisons)	Use a language feature that supports large integers (e.g., Python's arbitrary precision integers) or a hash of the tree structure to avoid comparisons of large numbers directly.
root contains many identical subtrees that could potentially match subRoot, but only one actually does	The algorithm should ensure that it correctly identifies the valid subtree and doesn't terminate prematurely on a false positive.