Same Tree

To determine if two binary trees are the same, you need to compare both the structure and the values of the corresponding nodes. Here’s a simple approach using recursion to check if two trees are the same:

  1. If both the current nodes are None, return True.
  2. If one of the nodes is None while the other is not, return False.
  3. If the values of the current nodes are not equal, return False.
  4. Recursively compare the left subtree of p with the left subtree of q.
  5. Recursively compare the right subtree of p with the right subtree of q.
  6. If all these conditions pass, return True.

Here’s the code:

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

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # If both nodes are None, they are the same
        if p is None and q is None:
            return True

        # If one of the nodes is None and the other is not, they are not the same
        if p is None or q is None:
            return False

        # If the values of the nodes are not the same, the trees are not the same
        if p.val != q.val:
            return False

        # Recursively compare left and right subtrees
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

The time complexity of this function is (O(n)), where (n) is the number of nodes in the tree, and the space complexity is (O(h)), where (h) is the height of the tree.

Identifying Problem Isomorphism

“Same Tree” can be mapped to “Subtree of Another Tree”.

In “Same Tree” problem, you have to determine if two given binary trees are exactly identical in structure and node values.

In “Subtree of Another Tree”, the problem is to identify whether one tree is a complete subtree of another. In essence, this problem involves a similar but slightly more complicated version of the “Same Tree” problem because it checks if a smaller tree is the same as any subtree in the larger tree.

Both problems require you to compare the structure and values of binary trees. “Same Tree” is simpler as you are only comparing two trees. “Subtree of Another Tree” adds complexity by asking if a smaller tree matches any subtree of the larger tree, not just the tree as a whole.

1
2
3
4
5

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[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

Problem Classification

  1. Binary Trees: The problem involves comparing two binary trees. Understanding how binary trees work, including concepts such as nodes, left and right children, is crucial to this problem.

  2. Tree Traversal: More specifically, this problem involves tree traversal as we need to compare each corresponding node in the two trees. It is a form of Depth-First Search (DFS) where you traverse the tree from the root, to the left subtree, and finally the right subtree.

  3. Recursion: The problem uses recursion to traverse and compare nodes in the binary trees. Recursion involves a function calling itself in its definition, which is a common approach to solve problems in tree data structures.

  4. Boolean Logic: The problem deals with boolean logic as we are checking whether two trees are the same, i.e., all corresponding nodes in the two trees are equal. This involves using logical AND and logical OR operations.

These classifications help to understand the underlying concepts and techniques typically used to solve such problems.

Language Agnostic Coding Drills

  1. Binary Trees: Understanding the concept of binary trees is crucial to this problem. This includes the concept of tree nodes, left and right children, and tree traversal methods.

  2. Recursion: This problem involves using recursion to solve the problem. Understanding the base and recursive cases in a recursive function is key.

  3. Conditional Statements: The if-else logic in this problem is simple yet crucial. It checks whether a node exists before accessing its properties.

Targeted Drills in Python

  1. Binary Trees:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

# Create a binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
  1. Recursion:
1
2
3
4
5
6
7

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

print(factorial(5))  # prints 120
  1. Conditional Statements:
1
2
3
4

# If statements
a = 5
if a > 3:
    print("a is greater than 3")

Problem-Specific Drill:

Now let’s combine all of these concepts into a drill specific to the problem at hand:

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

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

class Solution:
    def isSameTree(self, p, q):
        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

# Create binary trees
p = TreeNode(1)
p.left = TreeNode(2)
p.right = TreeNode(3)

q = TreeNode(1)
q.left = TreeNode(2)
q.right = TreeNode(3)

# Check if the trees are the same
solution = Solution()
print(solution.isSameTree(p, q))  # prints True

This drill exercises all the necessary concepts and builds up to the final solution. Each concept is demonstrated in isolation and then integrated into the final solution.

Coding Skill Exercise #26

Same Tree

Write a method to check if a given tree is the same tree.

Knowledge Gap Finder

If you are unable to code the solution, answer the following questions and reply to this email to get customized lesson.

Was the problem statement clear to you when you read it? What did you think of doing first? Were you reminded of a construct in general or a general structure of solution that you thought would be useful? Have you previously seen problems that resemble this one? Did you feel stuck at any point while working on this problem? What did you choose as your test case? Do you think you’ve covered all possible scenarios with your tests? What program design techniques did you apply to solve this problem? Are there any constructs of the programming language that you find difficult or confusing to use? What issues make programming constructs difficult to use? For example, the keyword used, the syntax, the examples, the documentation for the construct, etc.

Feel free to forward this email to your friends so they can subscribe here. https://codingskill.biz