Symmetric Tree

To check if a binary tree is symmetric, we need to ensure that the left subtree of the root is a mirror reflection of the right subtree of the root. We can do this by recursively comparing corresponding nodes in these two subtrees. Here’s a step-by-step guide:

If both the current nodes from the left and right subtrees are None, return True.
If one of the nodes is None while the other is not, or if the values of the nodes are not equal, return False.
Recursively compare the left child of the left subtree with the right child of the right subtree.
Recursively compare the right child of the left subtree with the left child of the right subtree.
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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.isMirror(root, root)

    def isMirror(self, left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
        # If both nodes are None, they are the same
        if left is None and right is None:
            return True

        # If one of the nodes is None and the other is not, or the values are not the same, they are not the same
        if left is None or right is None or left.val != right.val:
            return False

        # Recursively compare the left child of the left subtree with the right child of the right subtree
        # and the right child of the left subtree with the left child of the right subtree
        return self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)

This function’s time complexity 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.

 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
# 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
# @param {TreeNode} root
# @return {Boolean}
def wrapper(first, second)
  if first.nil? && second.nil?
    return true
  end
  if first.nil? || second.nil?
      return false
  end

  same = (first.val == second.val)
  left = wrapper(first.left, second.right)
  right = wrapper(first.right, second.left)
  
  return same && left && right
end

def is_symmetric(root)
  wrapper(root, root)
end

Identifying Problem Isomorphism

“Symmetric Tree” can be mapped to “Same Tree”.

Here’s why:

Both problems involve traversing trees and comparing nodes, but they do it in slightly different ways. In “Symmetric Tree”, we’re looking to see if the tree is a mirror image of itself. This means that we’re effectively comparing the left and right subtrees for each node to see if they are mirror images of each other.

In “Same Tree”, we’re comparing two different trees to see if they’re identical. This involves comparing the corresponding nodes in both trees to see if they are equal.

Both of these problems involve a depth-first traversal of the trees and a comparison of the nodes. The key difference is that in “Symmetric Tree”, we’re comparing nodes within the same tree, while in “Same Tree”, we’re comparing nodes in two different trees.

They both involve a simple depth-first traversal of the trees and comparison of nodes. “Symmetric Tree” is more complex due to the fact that it involves comparing mirrored nodes within the same tree.

Despite these differences, the fundamental structure and techniques used to solve these problems are very similar, hence the isomorphic mapping between them.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def isSymmetric(self, root):
        if not root:
            return true;

        return self.isSame(root.left, root.right)

    def isSame(self, leftroot, rightroot):

        if leftroot == None and rightroot == None:
            return True

        if leftroot == None or rightroot == None:
            return False

        if leftroot.val != rightroot.val:
            return False

        return self.isSame(leftroot.left, rightroot.right) and self.isSame(leftroot.right, rightroot.left)

Problem Classification

Binary Trees: The problem involves working with binary trees. Understanding the structure of binary trees including concepts of root, left child, and right child nodes is crucial.
Tree Traversal: This problem requires traversing a binary tree. This involves visiting each node in a tree in a specific order. Here, we’re checking for symmetry, which requires a kind of mirrored traversal of two subtrees.
Symmetry Checking: The problem requires checking whether the binary tree is symmetric around its center. This involves understanding the property of symmetry in the context of binary trees.
Recursion: The problem uses a recursive approach to solve the problem. A function within the solution refers to itself to solve smaller instances of the same problem.
Boolean Logic: This problem fundamentally requires determining a true or false value – whether or not a given binary tree is symmetric. This involves using logical operations like AND and OR to combine conditions.

This classification helps to understand the core concepts and techniques that underpin the problem, and can guide appropriate approaches to problem-solving and algorithm design.

Language Agnostic Coding Drills

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.
Tree Symmetry: This problem is specifically about determining whether a binary tree is symmetric. A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree.
Recursion: This problem involves using recursion to solve the problem. Understanding the base and recursive cases in a recursive function is key.
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

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(2)

Tree Symmetry:

For this concept, you should understand the symmetry property of a binary tree and how to check for it. However, writing code for this without using recursion would not be straightforward, so let’s move on to recursion.

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

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
25
26
27
28
29
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def isSymmetric(self, root):
        if not root:
            return True
        return self.isSame(root.left, root.right)

    def isSame(self, leftroot, rightroot):
        if leftroot == None and rightroot == None:
            return True
        if leftroot == None or rightroot == None:
            return False
        if leftroot.val != rightroot.val:
            return False
        return self.isSame(leftroot.left, rightroot.right) and self.isSame(leftroot.right, rightroot.left)

# Create a symmetric binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)

# Check if the tree is symmetric
solution = Solution()
print(solution.isSymmetric(root))  # 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.