100. Same Tree

I'm excited to cover this Leetcode algorithm for many reasons. For the first time, despite how minuscule it might seem, I was able to write out the steps solve this problem. This is a huge accomplishment for many reasons. There is often a disconnect in learning between seeing and doing. Especially when learning on your own, it's hard to strike a balance between watching others and tackling something on your own. Studying algorithms makes this just a challenging. So to be able to break down my thought process into coding steps to achieve a solution shows that I am witnessing a bridge between seeing and doing. I'm starting to find connections between my thought process and transferring it into code.

So lets dive into it:

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.

If we look at the first example, we can further understand what makes a tree structurally identical to another.

What makes a binary tree identical are the following:

• root nodes have the same value
• left subtree is identical
• right subtree is identical

This means that both trees must have the same number of nodes as well as the same value at every node's position. In this case, the left subtree has a value of two in both trees and the right subtree has a value of three in both trees.

In example one, we can see that trees p and q fulfill all the requirements to make them structurally identical.

Now that we understand what makes trees structurally identical, let's think about how we can solve this algorithm.

The solution I found will be a recursive solution called Depth First Search (DFS).
Depth First Search is the concept of choosing a node as a starting point and persist to the next neighboring nodes. When recurring from the first node to the next, the prior node is marked. In the wort case, all nodes will be visited at some point in this problem, therefor time complexity will be O (p + q) where the size of both trees will be added together.

Before we start coding, let's think of some base cases for this solution.

Lets say:

• If both trees are null, that means that they are the same, so we would return True.

 if not p and not q:
            return True

We are using conditional logic by using and to signify both p tree and q tree must be null to be True.

• If one tree is null and the other has a node, then they are not structurally identical, which would return False.

      if not p or not q or p.val != q.val:
            return False

Again we are using conditional by using or to say it doesn't matter which tree has a node or is null, hence we must return False.

• If there is a root, check the value of that node. If the vale is the same between trees p and q, return True. Otherwise, return False.

 return (self.isSameTree(p.left,q.left) and 
                (self.isSameTree(p.right, q.right )))

Now let's compile this all together to get our solution.

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

In the first "if" statement, we are implementing a base case to check if the trees are null. If both are null, it means they are structural identical and we return True. In the second "if" statement, we are checking our second base case that determines if one tree is null and the other has a node, then the values of trees p and q are not equal, so we return False. If the two trees are not null, and they have the same structure, it will be passed to the last two lines of our code. The last two lines will determine if there is a root, to check the values of the root and then continue throughout the subtrees to compare their values. If they are the same in value and structure, it will return True, otherwise it will be False.

Conclusion:
This is a note to all beginner coders, programmers, engineers, and developers, keep going. I haven't been practicing algorithms for very long and I'm still constantly bombarded with doubt throughout this process. But having that moment of enlightenment, where you can look at an algorithm and be a little less intimidated is an accomplishment within itself. There is so much to learn out there which makes it hard to be patient, but try not to let that stop you. When it comes to algorithms, try your best. If you get stuck, google it (that's part of our job!). Try to understand how you got to your answer and the code behind it and move on. Progress isn't a straight incline. You will be where you want to be in due time.

Resources: https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python

Comments

[geraldew]

I've been following this series on binary trees with interest for two reasons:

• the nostalgia for when I first learned about these structures, albeit with with Pascal and its explicit use of pointers to make the trees.
• some of the issues are a microcosm (a binary one) of the puzzles I had to solve for a file and folder analysis tool that I've written in Python.

To give an example of the similarity, here is a thought experiment about binary trees.

In the example you've given here, we start with two roots of binary trees that we want to check for being the same. Imagine instead, that these "same" binary trees were each mere sub-branches of larger binary trees that might be quite different from each other. Now consider that the challenge is to explore both of those larger binary trees and try to find if, and where, they hold that pair of "same" trees.

That was the problem I set out to solve, although for file system trees, which are n-ary rather than binary trees. I did solve it, but now I'm wondering whether tackling a binary tree equivalent would have led me to a different method.