BFS O(N) Solution | Python
Approach\n- Create a parent hash table (key: node | value: parent node)\n- Create a levels hash table to store the nodes at each height\n- Perform BFS normally 
# Approach\n- Create a `parent` hash table (key: node | value: parent node)\n- Create a `levels` hash table to store the nodes at each height\n- Perform BFS normally while storing the parents and nodes at each level\n- We can find the LCA by traversing upwards the leftmost and rightmost nodes of the last level. If both variables point to the same node, it means we found the LCA.\n\n# Code\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\n\nclass Solution:\n    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n        \n        from collections import deque, defaultdict\n\n        parents = {root: None}\n        levels = defaultdict(list)\n        max_depth = 0\n\n        queue = deque([(root, 0)])\n\n        while queue:\n            node, depth = queue.popleft()\n            levels[depth].append(node)\n            max_depth = max(max_depth, depth)\n            \n            if node.left:\n                parents[node.left] = node\n                queue.append((node.left, depth + 1))\n\n            if node.right:\n                parents[node.right] = node\n                queue.append((node.right, depth + 1))\n\n        leftmost = levels[max_depth][0]\n        rightmost = levels[max_depth][-1]\n\n        while leftmost != rightmost:\n            leftmost = parents[leftmost]\n            rightmost = parents[rightmost]\n        return leftmost\n\n```
['Breadth-First Search', 'Binary Tree', 'Python', 'Python3']