I will be chronicling my journey through Sean Prashed’s excellent LeetCode Patterns from Easy to Hard using my trusty programming language Python. Today we will be tackling the Same Tree question from LeetCode. As always, this is a solution and not the solution. The beauty of programming is that there are many approaches to the same result.
Task: 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.
Runtime Complexity: O(V) where V is the number of nodes
Let us imagine that we are given this task as a human. What we will most likely do is point our fingers at the nodes in equivalent positions and compare the values for each. If the values do not match, or if one node is not present where it should, we will conclude that the trees are not equal. This is the essence of this algorithm.
With dfsTogether function, we compare each equivalent node from the two trees. Given nodes p and q, there are four cases we need to consider:
- Both p and q are null. In this case, the two nodes are equal so we return true
- Only one of p or q is null. In this case, one node is missing where the other is present. The tree is not the same so we return false.
- The values for p and q are different. In this case, the values are different so the trees are different and we return false.
- The values for p and q are the same but we still have nodes left to explore. We call dfsTogether on the left and right nodes. We then return the ‘AND’ result of the two dfsTogether. If either of them returns false, this means that the tree is not the same.
The answer will propagate upwards the recursion. If at any point the nodes are not equivalent, the final answer will be false. Else, the final answer will be true.
Source Code: https://github.com/evangelato/LeetcodePatternsAdventure/blob/main/Easy/100_same_tree.py
