Subtree of Another Tree

To determine if subRoot is a subtree of root, we can perform a depth-first search (DFS) on the root tree. At each node, we’ll check if the subtree rooted at that node matches subRoot. Here’s a step-by-step guide to the algorithm:

  1. Match Trees: Create a function isMatch that takes two nodes and recursively checks if the subtrees rooted at those nodes are identical.

  2. Search for Subtree: In the main function, perform a DFS on root, and at each node, call isMatch to check if the subtree rooted at that node matches subRoot.

  3. Result: If a match is found, return True. If no match is found after searching the entire tree, return False.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:

        def isMatch(tree1, tree2):
            if not tree1 and not tree2: 
                return True
            if not tree1 or not tree2: 
                return False
            return tree1.val == tree2.val and isMatch(tree1.left, tree2.left) and isMatch(tree1.right, tree2.right)

        if not root: 
            return False
        if isMatch(root, subRoot): 
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

Explanation

  • isMatch Function: The isMatch function checks if two trees are identical. If both trees are empty, they are identical. If one is empty and the other is not, they are not identical. Otherwise, the values at the current nodes must be equal, and both left and right subtrees must also be identical.

  • Main Function: In the main function, you start DFS from the root of the main tree and call isMatch on the current node and subRoot. If a match is found, you return True. If you reach a leaf node and no match has been found, you return False.

  • Recursion: The main function is recursive, exploring both the left and right subtrees of the current node.

Insights

  • Time Complexity: The time complexity is (O(m \cdot n)), where (m) and (n) are the number of nodes in the main tree and the subtree, respectively.
  • Space Complexity: The space complexity is (O(m)) for the DFS call stack, where (m) is the number of nodes in the main tree.

This approach handles the case where the tree could be considered a subtree of itself, as mentioned in the problem statement, by returning True if both trees are empty.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s: 
            return False
        if self.isSameTree(s, t): 
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        return p is q

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def same?(s, t)
  if t.nil? && s.nil?
      return true
  end
  if s.nil? || t.nil?    
      return false
  end

  same = (s.val == t.val && same?(s.left, t.left) && same?(s.right, t.right))

  return same
end

def traverse(s, t)
    result = false
     if !s.nil? && !t.nil?
         result = same?(s, t) || traverse(s.left, t) || traverse(s.right, t)
     end
    return result
end
# @param {TreeNode} s
# @param {TreeNode} t
# @return {Boolean}
def is_subtree(s, t)
  traverse(s, t)
end

Problem Classification

This problem belongs to the “Binary Trees”.

The ‘What’ components:

  1. Two binary trees are given, root and subRoot.
  2. A ‘subtree’ in this context is defined as a node and all of its descendants in a binary tree.
  3. We need to check if there exists a subtree in root that has the same structure and node values as subRoot.

This is a “Tree Traversal” problem combined with “Tree Structure Comparison”. We’re required to traverse the tree root to find a subtree that matches the structure and values of subRoot. The problem involves concepts of tree traversal (e.g., depth-first search or breadth-first search) and recursive comparison of tree structures.

This is a “Pattern Searching” problem, where the pattern is the tree subRoot, and we are searching for this pattern in the larger tree root. It involves comparing each subtree in root with subRoot to check if they are identical. This comparison itself is a recursive process, which introduces the aspect of “Recursion” in the problem’s categorization.

The problem-solving process will likely involve recursively traversing the root tree, and at each node, checking if the subtree from that node matches the subRoot tree. This involves a comparison of the tree structures and values, which will also likely be implemented using a recursive process.

Language Agnostic Coding Drills

  1. Distinct Concepts:

a) Boolean logic: This concept deals with the use of boolean values (True or False) in conditional statements. It’s found in the “if not s” and “if self.isSameTree(s, t)” checks, as well as in the use of the “or” operator in the return statement of the “isSubtree” method.

b) Function Calls: This is about invoking functions to perform certain operations. The methods “isSubtree” and “isSameTree” are recursively called within their definitions to explore the binary trees.

c) Recursion: The recursive traversal of binary trees is a fundamental part of the solution. Both the “isSubtree” and “isSameTree” methods are called recursively to explore the left and right subtrees.

d) Binary Tree Traversal: This concept involves navigating through the nodes of a binary tree in a specific order. In this case, a kind of depth-first search is used to traverse through each node and its left and right children.

e) Object Access: This refers to accessing the attributes of an object, such as accessing the values and the left and right children of the tree nodes.

f) Tree Structure Comparison: The algorithm checks if two given trees have the same structure and the same node values, a crucial part of determining if one tree is a subtree of the other.

  1. Ordered Concepts:

a) Boolean logic: This is a foundational concept in programming, thus considered the easiest among the list.

b) Object Access: This is a simple operation once the data structure (in this case, the tree node) and its properties are understood.

c) Function Calls: Calling functions is a basic concept, but understanding when and how to call a function can be a bit more challenging, especially when recursive calls are involved.

d) Binary Tree Traversal: Understanding how to traverse a binary tree can be quite challenging for beginners, especially when it comes to choosing the correct traversal method.

e) Recursion: While recursion is a powerful tool, it can be difficult to grasp. Understanding the call stack and how recursion can be used to traverse data structures like trees requires a higher level of thinking.

f) Tree Structure Comparison: This is the most complex concept in this list. It involves not only traversing the tree but also making recursive comparisons of the tree structures.

  1. Problem-solving Approach:

a) The first step is to handle the base case for the recursion, i.e., if the tree ’s’ is empty, return False as an empty tree cannot contain a non-empty subtree.

b) We then check if the current tree ’s’ is the same as ’t’ using the “isSameTree” method. If they are the same, we return True.

c) If ’s’ is not the same as ’t’, we recursively call the “isSubtree” method on the left and right children of ’s’. This allows us to explore all possible subtrees in ’s’.

d) The “isSameTree” method checks if two given trees have the same structure and node values. This is done by recursively comparing the nodes and their children.

e) This recursive comparison continues until we’ve either found a matching subtree or explored all possible subtrees. If a match is found at any point, the algorithm returns True. If no match is found after exploring all subtrees, the algorithm returns False.

Each coding drill contributes to the final solution by either helping traverse the binary tree, making the necessary comparisons, or providing the recursive framework within which these operations take place. By integrating these drills in the correct order and with the correct conditions, we’re able to effectively solve the problem.

Targeted Drills in Python

  1. Python Coding Drills:

a) Boolean Logic:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

a = True
b = False

if a:
    print("a is True")

if not b:
    print("b is False")

if a or b:
    print("At least one of a and b is True")

b) Object Access:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

root = Node(1, Node(2), Node(3))

print(root.val)       # Accessing value
print(root.left.val)  # Accessing left child's value
print(root.right.val) # Accessing right child's value

c) Function Calls:

1
2
3
4

def hello():
    return "Hello, world!"

print(hello())

d) Binary Tree Traversal:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

def traverse(node):
    if node is None:
        return
    print(node.val)
    traverse(node.left)
    traverse(node.right)

root = Node(1, Node(2), Node(3))

traverse(root)

e) Recursion:

1
2
3
4
5
6
7

def factorial(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))

f) Tree Structure Comparison:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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

def is_same_tree(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False

    return (p.val == q.val and 
            is_same_tree(p.left, q.left) and 
            is_same_tree(p.right, q.right))

tree1 = Node(1, Node(2), Node(3))
tree2 = Node(1, Node(2), Node(3))

print(is_same_tree(tree1, tree2))  # Should return True
  1. Essential Problem-specific Concepts:

For this specific problem, the two crucial concepts are tree traversal and tree structure comparison. Understanding and being able to implement these concepts is essential as we need to traverse through the nodes of the given trees and compare their structure and values to determine if one tree is a subtree of the other.

  1. Integrating the Drills:

To solve the initial problem, we would start by creating the necessary helper function “isSameTree” that would allow us to compare two given trees for structural and value equality. This involves the use of recursion, tree traversal, and object access concepts.

Next, we would create the main function “isSubtree”. We would start by handling the base case for the recursion (if the tree is empty, return False). After this, we would check if the current tree is the same as the given subtree using the helper function “isSameTree”. This check would involve the use of function calls, boolean logic, and the problem-specific concept of tree structure comparison.

If the current tree is not the same as the subtree, we would proceed to recursively call the “isSubtree” function on the left and right children of the current tree. This step involves the use of recursion, tree traversal, function calls, and boolean logic.

The functions would keep calling themselves recursively until a match is found or all subtrees have been explored. Once all drills are integrated, the final function should be able to effectively determine if one tree is a subtree of the other.