100. Same Tree -LeetCode(Python)

I got you!

Problem:

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

Example 1:

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

Example 2:

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

Solution:

1. Recursive —

Explanation —

The base case of our recursion is when we have reached the leaf nodes at both the trees, in which case we return True, because the path terminated at the same time.

If, however, only either of the tree paths has been terminated or the value at present nodes in both the trees is not the same, we return False.

Finally, we call our function recursively on both the left and right subtrees and return the value of their AND operation.

Time and Space Complexity —

Also, the recursion stack could be storing all nodes in the tree in case of a really skewed tree (like a linked list). So, we assume the space complexity to be linear in the worst case.

Thus, if m and n are the number of nodes in the given binary trees,

Time Complexity: O(m+n)

Space Complexity: O(m+n)

2. Iterative —

Explanation —

We use a queue to store elements level wise from our trees.

At every step, we pop an element from the queue, which is just a pair of corresponding nodes in both the trees.

We then check if these nodes contain the same value. If yes, we append left children and right children of both the nodes as pairs into our queue.

If, however, we come across a pair that isn’t equal, we immediately return False.

The while loop terminates when all nodes in the tree have been traversed. So, now we can return True because no illegal pair was found while the BFS traversal.

Time and Space Complexity —

Also, our queue will be storing a maximum of (n / 2) nodes when it reaches the final level. So, we assume the space complexity to be linear in the worst case.

Thus, if m and n is the number of nodes in the trees,

Time Complexity: O(m+n)

Space Complexity: O(m+n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store