Coding Week 7 - Trees Flashcards
Problem 1)
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
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.
Diagram 1: https://drive.google.com/file/d/1C0uY5L_2wI_oFKuco8xJtp_NxfCkHI3X/view?usp=sharing
Diagram 2: https://drive.google.com/file/d/1hpMqa9zx4nd42gEZBlnOkXvXp0u8opRh/view?usp=sharing
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
Accepted
585,682
Submissions
1,273,609
Question 1)
The naive approach can solve this problem in O(N * M) time complexity. In the naive approach, we compare each subtree of the tree rooted at “root” with the tree rooted at “subRoot”. Is it possible to reduce this complexity to O(N + M)?
(N -> number of nodes in tree rooted at “root” and M -> number of nodes in tree rooted at “subRoot”)
A) Yes
B) No
A) Yes
This problem can be reduced to a pattern matching problem, hence we can use any linear pattern matching algorithm like z algorithm or KMP algorithm to solve this problem in O(N + M) time complexity.
Z algorithm - https://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/
KMP algorithm - https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
To convert the tree into a string, the correct serialization method would be to do a preorder or postorder traversal of the given trees with markers for the null values.
Example: 1
/ \
2 2
/ \
3 4
String value: #2#1#3#2#4#.
We also need to add another marker before adding a node’s value to overcome cases like:
Root: 2 Subroot: 22
Now they will have String values as 2## and 22## respectively. Now, since 2## is a substring of 22##, our approach will conclude that the first tree is a subtree of the second tree. However, this is not the case.
We can overcome this by adding a character (let it be ^, or simply space ) before adding the node’s value. Now, ^2## is not a substring of ^22##.
Problem 2)
Given the root of a binary tree, return the maximum average value of a subtree of that tree. Answers within 10-5 of the actual answer will be accepted.
A subtree of a tree is any node of that tree plus all its descendants.
The average value of a tree is the sum of its values, divided by the number of nodes.
Example 1:
https://drive.google.com/file/d/1eqqDArOy5a8ayJGtw0tcjiLlWWzSOenD/view?usp=share_link
Input: root = [5,6,1]
Output: 6.00000
Explanation:
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.
Question 1) Which Tree Traversal is the most intuitive to solve this problem?
A) Postorder
B) Preorder
C) Inorder
A) Postorder
To calculate average value of a subtree rooted at node, we need two things:
Sum of all values of the nodes in the subtree of node, let’s refer to it as ValueSum(node).
Count of the nodes in the node subtree, let’s refer to it as NodeCount(node).
Then, the average for subtree rooted at node will be ValueSum(node)/NodeCount(node).
Now, to calculate these values for a subtree rooted at node, we can derive them from the child nodes of node.
ValueSum(node) = ValueSum(node.left) + ValueSum(node.right) + Value(node)
NodeCount(node) = NodeCount(node.left) + NodeCount(node.right) + 1
Now, as we know we need the data about node.left and node.right to calculate the average of subtree rooted at node, and in postorder traversal we first traverse node.left and node.right and then the node. Hence, the postorder traversal is the most intuitive traversal to solve this problem.
Problem 2)
Given the root of a binary tree, return the maximum average value of a subtree of that tree. Answers within 10-5 of the actual answer will be accepted.
A subtree of a tree is any node of that tree plus all its descendants.
The average value of a tree is the sum of its values, divided by the number of nodes.
Example 1:
https://drive.google.com/file/d/1eqqDArOy5a8ayJGtw0tcjiLlWWzSOenD/view?usp=share_link
Input: root = [5,6,1]
Output: 6.00000
Explanation:
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.
Question 2) What will be the time and auxiliary space complexity of the most optimal approach?
(N -> Number of nodes in the tree)
A) Time - O(N ^ 2), Space - O(N)
B) Time - O(1), Space - O(1)
C) Time - O(N), Space - O(N)
D) Time - O(N), Space - O(1)
C) Time - O(N), Space - O(N)
Time will be O(N), because we visit each and every node only once, as we do in postorder traversal.
Space will also be O(N), because we will create N states for each of the nodes in the tree. Also, in cases where we have a skewed tree, we will implicitly maintain a recursion stack of size N, hence space complexity from this will also be O(N).
