Burning Tree

'''
Logic:We can do this while BFS traversal,so we can go down but we can't go up in tree so
we created a map in which we will store parent address and do bfs
similary created a visited map,which will take care of viisted nodes.
'''
'''
class Node:

    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None
'''
from collections import deque
def dfs(node, parent_map, target):
    if not node:
        return None

    target_node = None #it not found in left or right calls, target_node will return None
    if node.data == target:
        target_node = node

    if node.left:
        parent_map[node.left] = node
        left_target = dfs(node.left, parent_map, target)
        if left_target:
            target_node = left_target

    if node.right:
        parent_map[node.right] = node
        right_target = dfs(node.right, parent_map, target)

        if right_target:
            target_node = right_target

    return target_node

class Solution:
    def minTime(self, root, target):
        parent_map = {}
        target_node = dfs(root,parent_map,target)
        if not target_node:
            return 0
        q = deque([target_node])
        visited = {target_node}
        time = -1

        while q:
            for _ in range(len(q)):
                node = q.popleft()
                neighbors = [node.left,node.right,parent_map.get(node)]
                for neigh in neighbors:
                    if neigh and neigh not in visited:
                        visited.add(neigh)
                        q.append(neigh)
            time += 1
        return time

'''
Method 2:we can do this in single travesal by levelordertraversal storing parents in map
and when we acheived target we will start bfs algorithm from there.because we won't need
the parent of lower level nodes than the target level node.
'''
def dfs(node, target, ans):

    if not node:
        return -1, 0

    # Recursively get:
    # distance from target
    # height of subtree

    left_dist, left_height = dfs(node.left, target, ans)
    right_dist, right_height = dfs(node.right, target, ans)

    # Current subtree height
    curr_height = 1 + max(left_height, right_height)

    # If current node is target
    if node.data == target:

        # Burn time downward
        ans[0] = max(ans[0], max(left_height, right_height))

        return 1, curr_height

    # Target found in left subtree
    if left_dist != -1:

        # Fire reaches current node after left_dist seconds
        # Then burns right subtree
        ans[0] = max(ans[0], left_dist + right_height)

        return left_dist + 1, curr_height

    # Target found in right subtree
    if right_dist != -1:

        ans[0] = max(ans[0], right_dist + left_height)

        return right_dist + 1, curr_height

    # Target not found
    return -1, curr_height


class Solution:

    def minTime(self, root, target):

        ans = [0]

        dfs(root, target, ans)

        return ans[0]