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.

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Graph traversal

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:
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]


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]


class Solution:

	def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
		if not root:
			return None
		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, [])
		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)
		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):
			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]


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:
		(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)


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)

		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)


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


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


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)


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

		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


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)

		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


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


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)


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)