Learning Python with Interview Questions 3. Same Tree

Question. SameTree (LC 100)

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Resources: Leetcode

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Resources: Leetcode

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

• The number of nodes in both trees is in the range [0, 100].
• -104 <= Node.val <= 104

Understanding

What does mean ‘same tree’? From the root to leaf, given two trees have the same value in each node. The root from the root of each leaf should be the same. Or, if I overlap two trees, it would be exactly the same.

The base case that I can think of is the null tree case. if both given trees are null, it would return true? Yes

Example Tree — not the same tree case

Approach

I would think of a recursive way to solve this question. Simply traverse both trees and check if both nodes have the same value. otherwise, return false.

What if a tree is null but another tree is not null? it should return false. I think these are covered all cases to encounter when we traverse trees.

null? None!
I’ve encountered an error immediately when I enter null. :( Because there’s no null in python! instead, I found ‘None’. (case sensitive!) resource: link

recursive call or method call? self!
Another interesting thing to call the recursive call is that I need to add self before calling the function. Otherwise, Python can’t find the function name and keep showing ‘isSamaTree’ is not defined. resource: link
‘self’ references to the current instance of the class. To access the method call, I need to add the ‘self’.

Writing the code

I checked all false cases and added true conditions. Also, use None to check if the node is empty.

class Solution(object):
    def isSameTree(self, p, q):
        if p == None and q == None:
            return True
        if p == None or q == None:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

One of the interesting things is that I can use not for checking None case. It just a similar idea as !p && !q case. I slightly change the code. Also, combining two false cases for faster calculation.

class Solution(object):
    def isSameTree(self, p, q):
        if not p and not q:
            return True
        if (not p or not q) or (p.val != q.val):
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

The result seems slightly better.

Complexity

Time Complexity: Because I need to go through both trees once, the time complexity will be O(n).

Space Complexity: If the tree is an unbalanced tree, the stack will be O(n), but the best case — balanced tree case will be O(log(n))

Remark

The Same Tree question is a very famous interview question(One of the interviewers asked this question on co-op interview too!), and it is a good question to build an idea of how recursion works with Python.

Similar to other tree questions, this question also can be solved in an iterative way.