Same Tree Leetcode Problem 100 [Python Solution]

Question Link: Same Tree LeetCode Problem

Welcome back to another programming problem-solving session!

In today's guide, we will tackle the Same Tree problem, which is categorized as an easy problem on LeetCode.

This problem falls under the domain of trees and is often encountered in technical interviews, particularly with companies like Amazon.

Our goal is to determine whether two given binary trees, denoted as p and q, are the same or not.

To clarify, two binary trees are considered the same if they are structurally identical and their nodes have the same values.

Problem Overview

In this problem, we are presented with two binary trees, p and *q.

The task is to determine whether these two trees are identical in terms of structure and node values.

We must ensure that:

1. The structure of the trees is identical, meaning they have the same number of nodes and follow the same pattern of branching.
2. The values of the nodes in corresponding positions are the same.

Let's illustrate this with an example:

Example 1:

Input:
Tree p: [1, 2, 3]
Tree q: [1, 2, 3]

Output:
true

In this example, both p and q have the same structure and values in each node.

Hence, they are considered the same tree, and our function should return true.

Understanding Constraints

To provide a robust solution, it is essential to understand the constraints placed on the problem:

• The number of nodes in both trees is in the range [0, 100].
• Node values can range from -10^4 to 10^4. These constraints define the limits within which our solution must operate.

In the worst-case scenario, we might need to handle trees with up to 100 nodes, so efficiency is crucial.

Efficient Python Code Solution

Now, let's delve into an efficient Python solution to this problem.

We can achieve this by implementing a recursive function to compare the two trees.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # Base cases
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False

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

This Python code provides a clear and concise solution to the problem.

Here's a breakdown of how it works:

• We first define a TreeNode class to represent the nodes of the binary tree.
• The isSameTree function takes two tree nodes, p and q, as input arguments and returns a boolean value indicating whether they are the same.

Now, let's explore the code's logic:

• The function starts with base cases to handle situations where one or both of the nodes are None.

If both p and q are None, it implies that the current subtrees are structurally identical, and we return True.

If only one of them is None, the trees differ in structure, and we return False.

Additionally, if the values of the current nodes differ, we also return False.

• In the recursive step, we check the left and right subtrees of p and q.

For each pair of corresponding subtrees, we make a recursive call to isSameTree.

The recursive function will continue to check sub-subtrees until it reaches the base cases.

• The final result is determined by applying the logical and operation to the results of the recursive calls.

If both the left and right subtrees are the same, the function returns True, indicating that the entire trees are the same.

This elegant recursive solution ensures that the problem's constraints are met, and it provides an efficient way to compare binary trees.

Time and Space Complexity

To analyze the efficiency of our solution, let's consider the time and space complexities:

Time Complexity:
The time complexity of this solution is O(N), where N is the total number of nodes in both trees.

This is because, in the worst case, we may have to compare all nodes in both trees.

The recursive function traverses the entire structure, ensuring that no node is left unchecked.

Space Complexity:
The space complexity is O(H), where H is the height of the tree.

This space is used for the recursive call stack.

In the worst case, if the trees are highly unbalanced, the space complexity approaches O(N), but in well-balanced trees, it is closer to O(log N).

Reasoning Behind Our Efficient Approach

The reasoning behind our approach lies in the power of recursion.

We break down the problem of comparing two binary trees into smaller subproblems by recursively checking the left and right subtrees.

This divide-and-conquer strategy allows us to focus on comparing smaller tree structures and their corresponding node values.

In essence, the base cases handle scenarios where the trees are either empty or have structural differences.

Then, in the recursive step, we examine the left and right subtrees of p and q.

By applying the recursive function to these subtrees and combining the results with the and operation, we ensure that the entire trees are checked for equality.

This approach is not only efficient but also highly intuitive, leveraging the principles of recursion to solve the problem effectively.

Related Interview Questions By Company:

• Ugly Number LeetCode
• Subtree Of Another Tree LeetCode
• Maximum Number Of Balloons LeetCode

Related Interview Questions By Difficulty:

• Binary Tree Right Side View LeetCode
• Binary Tree Inorder Traversal LeetCode
• Construct Binary Tree From Preorder And Inorder Traversal LeetCode

Related Interview Questions By Category:

• Largest Number LeetCode
• Move Zeroes LeetCode
• Course Schedule Iv LeetCode

Conclusion

In this blog post, we've explored the Same Tree problem on LeetCode.

We've discussed the problem's requirements, constraints, and provided a clear and efficient Python solution using a recursive approach.

This solution ensures that we check both the structure and node values of two binary trees to determine if they are the same.

By understanding the base cases, recursion, and the logic behind our code, you can confidently tackle similar tree-related problems.

Additionally, we've analyzed the time and space complexities to evaluate the efficiency of our solution.

I hope this guide has been helpful in your journey to mastering binary tree problems.

If you found this content useful, please like, engage, and share it with others who might benefit from it.

Feel free to leave your comments, questions, and suggestions to foster a community of learners and problem solvers.

Happy coding, and best of luck with your programming endeavors!

Question Link: Same Tree LeetCode Problem