amazon DSA
Anonymous User
465

Question - Binary Tree on fire:
A binary tree catches a fire on all the leaf nodes. A node takes 1 second for it to burn and fall off the tree and it only falls of if it doesn't have any nodes under it. We want to take a snapshot of the tree every second for future analysis.
Find the leaves that fell of at each second.

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]] / [[5,4,3],[2],[1]]
1 1
/\
2 3
/
4 5

[4 5 3] , [2] , [1]

I gave approach ,like for each row , I will do binary search. find the index of first one and set max row and count of 1.

Topological sort is best approach.

Comments (5)