742. Closest Leaf in a Binary Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findClosestLeaf(self, root: TreeNode, k: int) -> int:
    """
    for Binary tree, if we need to check neighbour node which is not parent- children relationship, we probably need to convert binary tree to undirected graph. 
    In order to ensure leaf node is closest to target node k, use BFS  
    """
        # time O(N) space O(N)
        # Build graph, annotate leaves
        leaves = set()
        graph = collections.defaultdict(list)
        def preorder(node):
            if not node:
                return 
            # mark leaf node
            if not node.left and not node.right:
                leaves.add(node.val)
            if node.left:
                # undirected graph 
                graph[node.val].append(node.left.val)
                graph[node.left.val].append(node.val)
                preorder(node.left)
            if node.right: 
                graph[node.val].append(node.right.val)
                graph[node.right.val].append(node.val)
                preorder(node.right)
        preorder(root)
        # Graph traverse -BFS
        q = [k]
        while q:
            next_q = [] 
            # loop current q, update it's neighbour nodes.
            for node in q:
                # exit condition: find a leaf node
                if node in leaves:
                    return node
                next_q += graph.pop(node,[])# be careful to cases dictionary.pop(key) returns None
            q = next_q