[Top Interview 150] 100. Same Tree

Solution)

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def helper(root1, root2):
            if not root1 and not root2: return True

            if root1 and not root2: return False
            if not root1 and root2: return False
            
            leftRes = helper(root1.left, root2.left)
            rightRes = helper(root1.right, root2.right)

            return root1.val == root2.val and leftRes and rightRes
        
        return helper(p, q)

 
Problem: LeetCode
 
Time Complexity: O(2^n)
Space Complexity: O(n)

Explanation)

We'll use recursion for this problem.
 
There are 2 base cases.
1) Both of the roots do not exist
2) Only one of the roots does not exist.
 
Under the first case, if both roots do not exist, they are still identical so we'll return True.
However, under the second case, if only one of the roots exits, that means the two binary trees are structurally different. Thus we'll return False. 
 
We'll make recursive calls on the left/right subtrees of the root to figure out if the root's left/right subtrees are identical.
 
If the results of whether left/right subtrees are identical are found, we'll finally comare the values of the roots and return a boolean value of those 3 components.
 

Base Cases)

As we're using recursion, let's define a helper function.
 
Most of the recursive problems had one base case, but for this problem, we have two base cases to deal with as we're comparing two binary trees.
 
If both of the roots are Null, it indicates that the trees are empty. If they are both empty, they are structurally identical. Thus, we'll return True.
 
If ONLY one of the roots is Null, it indicates that only one of the trees is empty. If one has a root node but the other doesn't, they are not structurally identical. Thus, we'll return False.
 

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def helper(root1, root2):
            if not root1 and not root2: return True

            if root1 and not root2: return False
            if not root1 and root2: return False

 

Recursive Calls)

If we have dealt with the base cases, now we consider recursive calls. 
 
Let's assume that our helper function will return the result of whether two arbitrary binary trees are identical.
Then, in our recursive call section, let's get those results regarding the roots' left/right subtrees.
 

Recursive calls

If we retrieve those results, save them in variables for the next step. 
 

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def helper(root1, root2):
            if not root1 and not root2: return True

            if root1 and not root2: return False
            if not root1 and root2: return False
            
            leftRes = helper(root1.left, root2.left)
            rightRes = helper(root1.right, root2.right)

 

Final Comparison)

As we have the results of the left/right subtrees, the only leftover are the root nodes. Now we need to compare the root nodes' values.
 
To simplify things, as our final results, we'll return a combination of the root nodes' values and the left/right subtree results using and operator. 
 
Using and operator, if one of the results happen to be False, the statement will return False which is what we want.
 

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def helper(root1, root2):
            if not root1 and not root2: return True

            if root1 and not root2: return False
            if not root1 and root2: return False
            
            leftRes = helper(root1.left, root2.left)
            rightRes = helper(root1.right, root2.right)

            return root1.val == root2.val and leftRes and rightRes
        
        return helper(p, q)

 
 
I haven't solved binary tree in a while which got me scared a little, but it wasn't too bad. The only confusing part was the base cases. I was only thinking about both the root nodes being Null, which gave me a little trouble. If you're a beginner like me, it's always good to start with simplified thoughts instead of thinking recursion by recursion.
 
First, get the base cases. Then very simplified recursive calls. If such brief sketches are drawn, now you get to think recursion by recursion. That's how I try to solve recursion problems and how I got much better with these. Always simplifying recursions. Hope you have a great day.