Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.
Recall that:

The node of a binary tree is a leaf if and only if it has no children
The depth of the root of the tree is 0, and if the depth of a node is d, the depth of each of its children is d+1.
The lowest common ancestor of a set S of nodes is the node A with the largest depth such that every node in S is in the subtree with root A.

 
Example 1:
Input: root = [1,2,3]
Output: [1,2,3]
Explanation: 
The deepest leaves are the nodes with values 2 and 3.
The lowest common ancestor of these leaves is the node with value 1.
The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]".

Example 2:
Input: root = [1,2,3,4]
Output: [4]

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

 
Constraints:

The given tree will have between 1 and 1000 nodes.
Each node of the tree will have a distinct value between 1 and 1000.

Difficulty: interview

Starter code:

# 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 lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        

Solutions:
# 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 lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        
        def lca(root=root):
            if root:
                n1, d1 = lca(root.left)
                n2, d2 = lca(root.right)
                if d1 == d2:
                    return (root, d1 + 1)
                else:
                    return (n1, 1 + d1) if d1 > d2 else (n2, 1 + d2)
            return (None, -1)
        
        return lca()[0]
                        
                        
                
                


# 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 lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        
        def traverse(node):
            if not node:
                return 0, None
            hl, lcal = traverse(node.left)
            hr, lcar = traverse(node.right)
            if hl < hr:
                return hr + 1, lcar
            elif hl > hr:
                return hl + 1, lcal
            else:
                return hl + 1, node
            
        return traverse(root)[1]
        
        
        
        
                
        
    
    
    
    
    
    
    
    
    
    


# 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 lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        
        # get all paths
        paths = []
        def dfs(n, ps):
            nonlocal paths
            
            if not n:
                return
            if not n.left and not n.right:
                paths.append((len(ps), ps + [n]))
            if n.left:
                dfs(n.left, ps + [n])
            if n.right:
                dfs(n.right, ps + [n])
                
        dfs(root, [])
        # print(paths)
        
        # get longest paths
        paths = sorted(paths, key=lambda x: x[0], reverse=True)
        longest = []
        depth, path = paths[0]
        for d, p in paths:
            if d == depth:
                longest.append(p)
        # print([[x.val for x in xs] for xs in longest])
        
        # get the lowest common parent node
        if len(longest) == 1:
            return path[-1]
        for i in range(len(path)):
            if any(path[i] != p[i] for p in longest):
                break
        return path[i-1]
                
        
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        
        def helper(node):
            # at each node, return depth, lca
            if not node: return 0, None
            h1, lca1 = helper(node.left)
            h2, lca2 = helper(node.right)
            if h1 > h2: return h1+1, lca1
            if h2 > h1: return h2+1, lca2
            if h1 == h2: return h1+1, node
        
        return helper(root)[1]
            


from typing import Tuple

class Solution:
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        def lcaDeepestLeavesRecursive(node: TreeNode) -> Tuple[int, TreeNode]:
            if node is None:
                return (0, None)
            else:
                depthL, nodeL = lcaDeepestLeavesRecursive(node.left)
                depthR, nodeR = lcaDeepestLeavesRecursive(node.right)
                if depthL > depthR:
                    return (depthL + 1, nodeL)
                elif depthL < depthR:
                    return (depthR + 1, nodeR)
                else:
                    return (depthL + 1, node)

        return lcaDeepestLeavesRecursive(root)[1]

# 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 __init__(self): 
        self.max_depth = 0
        self.ancestor = None
        
        
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        if not root: 
            return root
        
        self.dfs(root, 0)
        return self.ancestor
        
    
    def dfs(self, node: TreeNode, curr_depth) -> int:   
        # return current deepest from that node? 
        curr_deepest_L, curr_deepest_R = curr_depth, curr_depth
        
        if not node.left and not node.right:
            if curr_depth > self.max_depth:
                self.max_depth = curr_depth
                self.ancestor = node
            return curr_depth
        
        if node.left:
            curr_deepest_L = self.dfs(node.left, curr_depth + 1)
        if node.right: 
            curr_deepest_R = self.dfs(node.right, curr_depth + 1)
        
        if curr_deepest_L == curr_deepest_R == self.max_depth: 
            self.ancestor = node
        
        return max(curr_deepest_L, curr_deepest_R)
        


# 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 lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        def get_depth(root):
            if not root: return 0
            else:
                return max(get_depth(root.left), get_depth(root.right))+1
        max_depth = get_depth(root)
        
        # print(max_depth)
        def dfs(root, depth):
            if not root: return root
            if get_depth(root.left) == get_depth(root.right) == depth-1:
                return root
            return dfs(root.left, depth-1) or dfs(root.right, depth-1)
        
        return dfs(root, max_depth)

# 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:
\tdef lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
\t\treturn self.helper(root)[1]
\tdef helper(self,root):
\t\tif not root:
\t\t\treturn (0,None)
\t\tlevleft,lcal=self.helper(root.left)
\t\tlevright,lcar=self.helper(root.right)
\t\tif levleft>levright:
\t\t\treturn (levleft+1,lcal)
\t\telif levleft<levright:
\t\t\treturn (levright+1,lcar)
\t\treturn (levleft+1,root)

# 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 lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        def traverse(root, level):
            if root:
                if not root.left and not root.right:
                    return level, root
                else:
                    left_level, left_lca = traverse(root.left, level + 1)
                    right_level, right_lca = traverse(root.right, level + 1)
                    if left_level == right_level:
                        return left_level, root
                    elif left_level > right_level:
                        return left_level, left_lca
                    else:
                        return right_level, right_lca
            return float('-inf'), None

        deepest_level, lca = traverse(root, 0)
        return lca

# 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 lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        dic = {}
        explore = [root]
        nextlevel = []
        while explore:
            leaf = explore
            for node in explore:
                if node.left:
                    dic[node.left] = node
                    nextlevel.append(node.left)
                if node.right:
                    dic[node.right] = node
                    nextlevel.append(node.right)
            explore, nextlevel = nextlevel, []
        
        newleaf = set()
        while len(leaf) > 1:
            for node in leaf:
                newleaf.add(dic[node])
            
            leaf, newleaf = newleaf, set()
        
        for res in leaf:
            return res

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#   1
# /   \\
# 2    3

# [1, 2,null, null,3, null, null]

class Solution:
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
      return self.helper(root)[0]
        
    def helper(self, root):
        if not root:
            return None, 0
        n1, l1 = self.helper(root.left)
        n2, l2 = self.helper(root.right)

        if l1 > l2:
            return n1, l1+1
        elif l1 < l2:
            return n2, l2+1
        else:
            return root, l1+1


# 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 lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        node0, node1 = None, None
        q = [root]
        while q:
            node0, node1 = q[0], q[-1]
            q = [child for node in q for child in (node.left, node.right) if child]
        if node0 == node1:
            return node0
        result = None
        # NodeWithStatus = collections.namedtuple('NodeWithStatus', ['node','status'])
        def lca(root: TreeNode) -> bool:
            nonlocal result
            if root is None:
                return False
            left = lca(root.left)
            right = lca(root.right)
            if left and right:
                result = root
            return (root == node0 or root == node1) or left or right
        lca(root)
        return result


# 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 lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        
        def getDepth(root):
            if not root: return 0
            return 1 + max(getDepth(root.left), getDepth(root.right))
        
        maxDepth = getDepth(root)
        #print(maxDepth)
        def helper(root, d):
            nonlocal ans, maxDepth
            if not root: return 0
            
            left = helper(root.left, d+1)
            right = helper(root.right, d+1)
            
            if left == right and left == maxDepth-d-1:
                ans = root
            
            return 1 + max(left, right)
        
        ans = None
        helper(root, 0)
        return ans
        


# 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

from collections import defaultdict


class Solution:
    def __init__(self):
        self.deepest = -1
        self.m = defaultdict(list)
        
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        self.dfs(root, 0)
        
        if self.deepest == -1:
            return None
        if len(self.m[self.deepest]) == 1:
            return self.m[self.deepest][0]
        return self.lca(root, self.m[self.deepest])
    
    def dfs(self, node, level):
        if node is None:
            return
        if level not in self.m:
            self.m[level] = []
        self.deepest = max(self.deepest, level)
        self.m[level].append(node)
        self.dfs(node.left, level+1)
        self.dfs(node.right, level+1)
        
    def lca(self, x, nodes):
        if x is None:
            return x
        for node in nodes:
            if node == x:
                return x
        left = self.lca(x.left, nodes)
        right = self.lca(x.right, nodes)
        if left is not None and right is not None:
            return x
        return left if left is not None else right

# 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
from collections import defaultdict

class Solution:
    def __init__(self):
        self.mapper = {}

    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        if not root:
            return None

        self.traverse_tree(root, [])
        
        for key, vals in self.mapper.items():
            print(f'{key}: {[item.val for item in vals]}')
        
        lst_of_nodes = list(self.mapper.values())
        if len(lst_of_nodes) == 1:
            return lst_of_nodes[0][-1]
        
        common = None
        length = max(map(len, lst_of_nodes))
        
        for i in range(length):
            curr = None
            for nodes in lst_of_nodes:
                if len(nodes) < length:
                    continue
                if not curr:
                    curr = nodes[i]
                    continue
                if curr == nodes[i]:
                    continue
                else:
                    return common
            common = curr
        return common
                
        
                

                
        
    def traverse_tree(self, node: TreeNode, ancestors: list) -> None:
        if not node:
            return
        new_lst = ancestors.copy()
        new_lst.append(node)
        if not node.left and not node.right:
            self.mapper[node.val] = new_lst
        
        self.traverse_tree(node.left, new_lst)
        self.traverse_tree(node.right, new_lst)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        def height(root):
            if not root:
                return 0
            return 1+max(height(root.left),height(root.right))
        if height(root.left)==height(root.right):
            return root
        elif height(root.left)>height(root.right):
            return self.lcaDeepestLeaves(root.left)
        return self.lcaDeepestLeaves(root.right)