572. Subtree of Another Tree — LeetCode(Python)

I got you!

Problem:

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

Constraints:

  • The number of nodes in the root tree is in the range [1, 2000].
  • The number of nodes in the subRoot tree is in the range [1, 1000].
  • -104 <= root.val <= 104
  • -104 <= subRoot.val <= 104

Solution:

identical() helper function —

Consider reading my solution for 100. Same Tree — LeetCode(Python) to better understand the code above.

We need a helper function to judge if the two subtrees we are considering are in-fact identical.

1. Iterative Approach (BFS) —

Explanation —

A queue is used to store all nodes in the tree level by level.

At every step, we pop / dequeue an element from the queue. If this node has a value equal to that of the subTree’s root, we check if both the subtrees are identical or not. True is returned if they are.

The, we append the left and right children of the current node into our stack.

The while loop terminates when the queue is empty, which means all nodes in the tree have been traversed and popped out from the queue.

So, now it is safe to say that no such subtree was found in our given tree. Therefore, we return False.

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, per tree — therefore, quadratic.

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

Time Complexity: O(mn)

Space Complexity: O(mn)

2. Recursive Approach (DFS) —

Explanation —

We simply return True if the subTree is empty, because then our tree will have a copy of it. [this clause can be omitted because we are given that the subTree will have a positive number of nodes]

The base case of our recursion would be when we reach a leaf node in our tree, which is when we return False.

Else, we check if the current node in the tree is where our subTree is rooted at. If yes, we return True.

Otherwise we return the value of the recursive search on the left and right children of the current node.

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, per tree — therefore, quadratic.

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

Time Complexity: O(mn)

Space Complexity: O(mn)

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