Interview Question
Country: United States
/*
The tree will burn in k ms, where k is the diameter of the tree.
The below is not a formal proof ( and may be wrong!)
Find the diameter (k) of the tree and let the sequence of nodes
{N0, N1, N2,..Nj, Nj+1, ..,Nk} lie on the diameter (path).
Let us consider the following possibilities how the fire could be
started
Case (1):
The fire could be lit at node N0 or Nk and would take the
maximum hops to reach the other end of the diameter.
Also, think of the intermediate burnt state of the tree
where the fire has reached node Nj. Now the remaining part
of the diameter left intact is k-j. Can there exist any reachable
node at a distance greater than k-j from Nj ? The answer is no.
Because, this would be contradict the definition of diameter.
If such a node existed, then it would be included on/in the diameter
path. We can safely conclude that all nodes reachable from Nj will
burn before the fire reaches the other end of the diameter, Nk.
It is clear in this case that the fire would consume the tree in
just k ms
Case (2):
The fire is started at a leaf node, Nx, not in {N0, N1, N2,..Nj, Nj+1, ..,Nk}
In this case, the fire has to eventually reach a node on the diameter path.
Let the fire with source at Nx reach Nj on the diameter path. Let the difference
between path length (N0..Nj) and path length (Nx...Nj) be D'.
After reaching Nj, the fire will continue towards Nk will will take
path length ( Nj.. Nk) ms. So the tree will be consumed in (k MINUS D') ms
*/
Assuming we are given parent pointer in the tree:
Apply DFS from the leaf node (including the parent), add 1 ms for all nodes in your path until you reach end and recurse back to node where you started. Node keeps max cost after recursive return to itself, and returns that to its calling node. Once reached back to the leaf node, returned cost is the answer.
#include <bits/stdc++.h>
- manjuransari143 September 07, 2018using namespace std;
struct Node {
int data;
Node *left, *right;
};
Node* newNode(int data) {
Node *temp = new Node();
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
int minTimeUtil(unordered_map<Node*, int> &minTime ,Node *root) {
if(root) {
minTimeUtil(minTime, root->left);
minTimeUtil(minTime, root->right);
if(root->left == NULL && root->right == NULL)
minTime[root] = 1;
else {
minTime[root] = min(root->left!=NULL?minTime[root->left]:INT_MAX, root->right!=NULL?minTime[root->right]:INT_MAX) + 1;
}
}
}
int main()
{
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->right = newNode(8);
root->left->left->left = newNode(6);
root->left->left->right = newNode(7);
unordered_map<Node*, int> minTime;
minTimeUtil(minTime, root);
int ans = 0;
for(auto n:minTime) {
cout<<n.first<<" "<<n.second<<endl;
ans = max(ans, n.second);
}
cout<<ans<<endl;
return 0;
}