CareerCup

public class Solution {

    public static class Node {
        int value;
        Node left;
        Node right;
    }

    public int timeTilBurns(Node root, Node start) {
        if (root == null || start == null) return 0;

        Map<Node, Node> nodesAndParents = new HashMap();
        findParensForAllNodes(root, null, nodesAndParents);

        int time = 0; // current moment
        
        List<Node> currentBurningNodes = new ArrayList() {{ add(start); }}; 
        
        while (!nodesAndParents.isEmpty()) {
            
            List<Node> newCurrentBurningNodes = new ArrayList();
            
            // infect neighbours
            while (!currentBurningNodes.isEmpty()) {
                
                Node currentBurning = currentBurningNodes.remove(0);
                
                // add infected nodes
                Node parent = nodesAndParents.get(currentBurning);
                if (parent != null) newCurrentBurningNodes.add(parent);
                if (currentBurning.left != null) newCurrentBurningNodes.add(currentBurning.left);
                if (currentBurning.right != null) newCurrentBurningNodes.add(currentBurning.right);

                nodesAndParents.remove(currentBurning);
            }

            time++;
            currentBurningNodes = newCurrentBurningNodes;
        }

        return time;
    }

    public void findParensForAllNodes(Node node, Node parent, Map<Node, Node> map) {
        if (node != null) {
            map.put(node, parent);
            findParensForAllNodes(node.left, node, map); 
            findParensForAllNodes(node.right, node, map); 
        }
    }
}

O(n) approach -

public static void main(String[] args){
	  
	    T N10 = new T(12, null, null);
	    T N9 = new T(11, null, null);
	    T N8 = new T(3, N10, null);
	    T N7 = new T(10, null, null);
	    T N6 = new T(9, null, null);
	    T N5 = new T(8, null, null);
	    T N4 = new T(7, N8, N9);
	    T N3 = new T(6, N6, N7);
	    T N2 = new T(5, N4, N5);
	    T N1 = new T(4, N2, N3);
	    
	    int startFire = 9;
	    height(N1);
	    int left = catchFire(N1.left, startFire, -1);
	    if(left == -1)
	      left = N1.leftHt-1;
	    else
	    	left = N1.leftHt - left;
	  
	    int right = catchFire(N1.right, startFire, -1);
	    if(right == -1)
	      right = N1.rightHt-1;
	    else
	    	right = N1.rightHt - right;
	  
	    System.out.println((left+right+1));
	    
	  }
	  
	  
	  public static int catchFire(T node, int startFire, int fireHt){
	  	if(node == null)
	      return fireHt;
	    
	    fireHt = catchFire(node.left, startFire, fireHt);
	    fireHt = catchFire(node.right, startFire, fireHt);
	    
	    if(node.left != null && node.left.val == startFire)
	      fireHt = node.height-1;
	    if(node.right != null && node.right.val == startFire)
	      fireHt = node.height-1;
	    
	    return fireHt;
	  }
	  
	  public static void height(T node){
	  	if(node == null)
	      return;
	    height(node.left);
	    height(node.right);
	    
	    if(node.left != null && node.right != null){
	    	node.height = Math.max(node.left.height, node.right.height) +1;
	    	node.rightHt = node.right.height +1;
	    	node.leftHt = node.left.height +1;
	    }
	    else if(node.left != null){
	    	node.height = node.left.height+1;
	    	node.leftHt = node.left.height+1;
	    }
	    else if(node.right != null){
	    	node.height = node.right.height+1;
	    	node.rightHt = node.right.height+1;
	    }
	  }
	  
	  
	  static class T{
	  	int val;
	    T left;
	    T right;
	    int height;
	    int rightHt;
	    int leftHt;
	    
	    public T(int val, T left, T right){
	    	this.val = val;
	      	this.left = left;
	      	this.right = right;
	    }
	  }

probably there is no parent pointer in the node, since the problem would be trivial that way (as mentioned in the question).

Maybe some observations are interesting:
- If the fire starts at the root, it takes the trees hight time. to burn down the whole tree.
- If the fire starts on the left branch of the root, it takes max(height of the left branch, 2 + height of right branch)
- we can recursively formulate the problem for each root:

if it starts the fire:
	burn-time = max(height(left) + 1, height(right) + 1)

if it doesn't start fire, but one of it's sub-trees start the fire:
	burn-time = max(burn-time-fire-starting sub-tree, height other sub-tree + 1 + distance from fires-tarting node + 1)
if it doesn't start the fire and neither the left nor the right subtree starts the fire:
	return the height (max left-height, right-height)

in code, if I didn't miss a count, that's the kind of things one should better check carefully, but i actually only wanted to post the idea

struct BurnDownState {
	int height; // height of (sub)tree
	int distFromFireStart; // if tree starts fire, distance to the fire starting node
	int burnDownTime; // time needed to burn that tree
};
BurnDownState burnDownTimeRec(Node* root, Node* fireStart) 
{
	if(root == nullptr) return {0, -1, -1};
	auto ls = burnDownTime(root->left, fireStart);
	auto rs = burnDownTime(root->right, fireStart);
	if(root == fireStart) {
		return {1 + max(ls.height, rs.height), 0, max(ls.height, rs.height)};
	}
	if(rs.distFromFireStart >= 0) swap(ls, rs); // avoid redundant code below for rs
	if(ls.distFromFireStart >= 0) {
		return {1 + max(ls.height, rs.height), ls.distFromFireStart + 1, 
				max(ls.burnDownTime, ls.distFromFireStart + 1 + rs.height)};
	}
	return {1 + max(ls.height, rs.height), -1, -1};
}

int burnDownTime(Node* root, Node* fireStart) 
{
	return burnDownTimeRec(root, fireStart).burnDownTime;
}

I would solve this problem using recursion. I haven't tested the code but I think it should illustrate the idea.

const timeToCatchFire = (stack, cycle = 1, visited = new Set()) => {
    const newGen = [];
    for(node of stack) {
        addAdjacents(node, newGen, visited);
    }
    if(newGen.length > 0)
        return timeToCatchFire(newGen, cycle + 1, visited);
    else
        return cycle;
}

const addAdjacents = (node, stack, visited)  => {
    if(node.parent && !visited.has(node.parend))
        stack.push(node.parent);
    if(node.parent && !visited.has(node.parend))
        stack.push(node.parent);
    if(node.parent && !visited.has(node.parend))
        stack.push(node.parent);
}