Variation of Same Binary Tree Solutions

Since I noticed my weakness in recursion and tree problems, I decided to go back to the basics of binary search trees to build up my skills and confidence. One thing I realized is that a solution for one problem can often be a method for solving another.

LeetCode 100: Same Tree

This is a fundamental question that checks whether two given trees are the same.

Once again, the solution requires recursion, and despite my efforts, I had to refer to the answer after an hour of trying. Yes, I can write real-world programs, yet I still struggle with an easy LeetCode problem. The answer was actually quite straightforward, and I probably overcomplicated things:

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q: # both None
            return True

        if not p or not q: # one is None and the other is not
            return False

        if p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        
        return False

Breaking It Down

If both nodes are None: They are the same.
If one is None and the other is not: They are different.
If both exist and have the same value: Recursively check their left and right children.
Otherwise: They must be different, so return False.

LeetCode 101: Symmetric Tree

The main difference here is that instead of checking whether two trees are identical, we check whether a tree is symmetrical.

class Solution:
    def isMirror(self, left, right):
        if not left and not right:
            return True

        if not left or not right:
            return False
        
        if left.val == right.val:
            return self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)

        return False
        
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.isMirror(root.left, root.right)

Notice the similarities? The only difference is how we pass the next nodes in a mirrored fashion to check for symmetry.

LeetCode 572: Subtree of Another Tree

This problem is another variation of the "Same Tree" problem, except we need to check if one tree is a subtree of another.

class Solution:
    def isSameTree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root and not subRoot:
            return True
        if not root or not subRoot:
            return False
        if root.val == subRoot.val:
            return self.isSameTree(root.left, subRoot.left) and self.isSameTree(root.right, subRoot.right)
        return False

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root:
            return False
        if not subRoot:
            return True
        if self.isSameTree(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

Here, we reuse the isSameTree method and apply it to check whether the root itself is a subtree. If not, we recursively check its left and right branches.

Final Thoughts

All three of these problems are categorized as LeetCode "Easy," and I would say that's fair. It’s really about recognizing how we can modify a simple base algorithm to fit different conditions. My biggest challenge seems to be overthinking, especially with easy problems.

But hey, practice makes perfect, right? I’ll keep at it and hopefully improve my skills. Until next time!

Prev Next