L31. Minimum time taken to BURN the Binary Tree from a Node | C++ | Java

#treeSeries #striver #placements

[takeUforward]

Please likeeee, shareeee and :) Also follow me at Insta: Striver_79

[sparshsharma]

This problem was exactly similar to that of the previous one, yet there was no difference in your enthusiasm or efforts in explaining the solution. Hats off bhaiya!! And yes, likeeeed, shareeeed, and understood🔥🔥

[nitinkumarsingh]

you can also try it by slighly different approach. After making parent map, instead of taking another bfs to find the time, You can find the height of tree using dfs cosidering target node as root node and also taking the help of visited map. The code of this part is similar to find the height or bt with slight modification.

Code:
int height(Node* root, unordered_map<Node*, Node*>&par, unordered_map<Node*, int>&vis)
{
if(!root)
return 0;

vis[root]=1;

int lh= INT_MIN;
int rh= INT_MIN;
int ph= INT_MIN;

if(!vis[root->left])
lh= height(root->left, par, vis);
if(!vis[root->right])
rh= height(root->right, par, vis);
if(!vis[par[root]])
ph= height(par[root], par, vis);

return max(ph, max(lh, rh)) +1;
}

The final ans will be height-1;

[arvindersingh]

I think we can use dfs, since it is a tree not graph (ie acyclic), here ans would be max of all depths from start node, simply max of distance you can go from start, while maintaining visited. For parent mapping, obviously bfs is only option. However, bfs is more natural as intuitive to come up with, but dfs is also possible approach to follow after parent mapping.

[ahmedadebisi]

It makes me sooo happy that I could apply the technique in the previous video to solve this problem. Kudos striver!! ❤️

[uRamPlus]

Self Notes:
🍊 Mark each node to its parent to traverse upwards in a binary tree
🍊 We will do a BFS traversal from our starting node.
🍊 Traverse up, left, right until 1 radial level (adjacent nodes) are burned and increment our timer.

[sarangtamrakar]

Just based on Print all the node from given node understanding I am able to write same exact code logic... Thnaks for making learning very smooth..

[ankitbansal]

I've never explained anything as beautifully and easily as this during my entire time in college, like you do.Thank u so much ❤

[sujoyseal]

Which ever node in the tree burns first, we can imagine that node to be the root . We can do a level order traversal from this node . The number of levels is the required answer since all nodes in the same level burns at the same time.

[manusisodia]

Great...
struggling with this problem
And concluded now that this is a simple hashing and level order line by line problem 🙂

[tapeshvashisth]

Great solution! This is my dfs solution for this question 😅

typedef BinaryTreeNode<int> node;

int ans = 0;

int helper(node * root, int target) {
if (root) {
int left = helper(root->left, target);
int right = helper(root->right, target);

if (root->data == target) {
ans = max(abs(left), max(abs(right), ans));
return 1;
}

if (left <= 0 && right <= 0) {
return min(left, right) - 1;
} else {
ans = max(ans, abs(left) + abs(right));
return left > 0 ? left + 1: right + 1;
}
} else {
return 0;
}
}

int root, int start)
{
ans = 0;
helper(root, start);
return ans;
}

[eklavyaprasad]

Thank You Bhaiya for the amazing explanation. I watched the prev. video of allNodesAtKthDistance form a node and paused this video and applied your logic and got it right.

[DevanshVerma-uv]

crisp and concise, so well explained!👏

[Weirdvloggertrue]

Woah!! 🔥❤️
This type of variations in questions requires a lot of research and hard work.

Hats off to you. Great work👏

I'll be watching the entire series and will make sure that I solve any question of trees topic.

Thanks for everything 🙂❤️

[PrinceKumar-elob]

A quick observation here striver -> Instead of using if(f1) time++;
we know that at last leaf node will not be able to burn anyone then why don't we
just return time-1 .
Instead of writing 5 lines of code returning time-1 is sufficient. It
passed all test case on interview bit and seems logical to me .

[rahularity]

This solution is not accepted in Interviews, It is simply make the graph out of the given tree and now the solution is easy.
In interviews it will be required to solve it without making a graph. (i.e, . without extra space)

[VineetKumar-fkrl]

Solved this question by own bcz of previous question, very happy 😊.
Thanks striver for your invaluable content!!!

[Rider]

class Solution {
public:
unordered_map<int, Node*> parent; // Map child value -> parent node

Node* findtargetpointer(Node* root, int target) {
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
if (temp->data == target) return temp;
if (temp->left) q.push(temp->left);
if (temp->right) q.push(temp->right);
}
return nullptr; // Handle case where target is not found
}

void buildParentMap(Node* root) {
if (root == NULL) return;

queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* temp = q.front();
q.pop();

if (temp->left) {
parent[temp->left->data] = temp; // Map left child to parent
q.push(temp->left);
}
if (temp->right) {
parent[temp->right->data] = temp; // Map right child to parent
q.push(temp->right);
}
}
}

void cal_dist(Node* target, int& maxDist) {
unordered_set<int> visited; // Keep track of visited nodes
queue<Node*> q;
q.push(target);
visited.insert(target->data);

while (!q.empty()) {
int size = q.size();
bool expanded = false; // Track if any new nodes are added at this level

while (size--) {
Node* temp = q.front();
q.pop();

// Add left child if not visited
if (temp->left && == visited.end()) {
q.push(temp->left);

expanded = true;
}

// Add right child if not visited
if (temp->right && == visited.end()) {
q.push(temp->right);

expanded = true;
}

// Add parent if not visited
if (parent.find(temp->data) != parent.end() && == visited.end()) {
q.push(parent[temp->data]);

expanded = true;
}
}

if (expanded) maxDist++;
}
}

int minTime(Node* root, int targetValue) {
Node* target = findtargetpointer(root, targetValue);
if (!target) return 0; // If target node is not found, return 0

buildParentMap(root); // Build parent-child relationships

int maxDist = 0;
cal_dist(target, maxDist); // Calculate maximum distance
return maxDist;
}
};

[cinime]

Understood! So wonderful explanation as always, thank you very much!!

[satyamsrivastava]

I just saw the half video and written the whole code for this problem and that was accepted.. Your videos are damm good