Given the root of a binary tree, the depth of each node is the shortest distance to the root.
Return the smallest subtree such that it contains all the deepest nodes in the original tree.
A node is called the deepest if it has the largest depth possible among any node in the entire tree.
The subtree of a node is tree consisting of that node, plus the set of all descendants of that node.
 
Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

Example 2:
Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree.

Example 3:
Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.

 
Constraints:

The number of nodes in the tree will be in the range [1, 500].
The values of the nodes in the tree are unique.

Source: leetcode | Difficulty: MEDIUM_HARD
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 subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        

Solutions:
class Solution:

	def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:

		def dfs(node, depth):
			if not node:
				return (node, depth)
			(left, l_depth) = dfs(node.left, depth + 1)
			(right, r_depth) = dfs(node.right, depth + 1)
			if l_depth > r_depth:
				return (left, l_depth)
			if r_depth > l_depth:
				return (right, r_depth)
			return (node, l_depth)
		return dfs(root, 0)[0]


class Solution:

	def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:

		def helper(root):
			if not root:
				return (None, 0)
			(left, h_l) = helper(root.left)
			(right, h_r) = helper(root.right)
			if h_l == h_r:
				return (root, h_l + 1)
			return (left, h_l + 1) if h_l > h_r else (right, h_r + 1)
		(node, _) = helper(root)
		return node


import heapq

class Solution:

	def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
		nodes = []
		self.counter = 0

		def dfs(root, nodes, depth):
			if not root.left and (not root.right):
				heapq.heappush(nodes, (-depth, self.counter, root))
				self.counter += 1
			if root.left:
				dfs(root.left, nodes, depth + 1)
			if root.right:
				dfs(root.right, nodes, depth + 1)
		dfs(root, nodes, 0)
		deepestNodes = []
		foundArr = []
		maxDepth = nodes[0][0]
		while nodes and nodes[0][0] == maxDepth:
			deepestNodes.append(heapq.heappop(nodes)[2])
			foundArr.append(False)

		def helper(root, deepestNodes, foundArr):
			for i in range(len(deepestNodes)):
				if root == deepestNodes[i]:
					foundArr[i] = True
					break
			leftArr = foundArr[:]
			rightArr = foundArr[:]
			leftFound = False
			rightFound = False
			if root.left:
				resLeft = helper(root.left, deepestNodes, leftArr)
				leftFound = True
				for i in leftArr:
					if not i:
						leftFound = False
						break
			if root.right and (not leftFound):
				resRight = helper(root.right, deepestNodes, rightArr)
				rightFound = True
				for i in rightArr:
					if not i:
						rightFound = False
						break
			found = True
			for i in range(len(foundArr)):
				foundArr[i] = foundArr[i] or leftArr[i] or rightArr[i]
			if leftFound:
				return resLeft
			elif rightFound:
				return resRight
			for i in foundArr:
				if not i:
					found = False
					break
			if found:
				return root
			else:
				return None
		return helper(root, deepestNodes, foundArr)


class Solution:

	def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:

		def getDepth(root):
			if not root:
				return 0
			left = getDepth(root.left)
			right = getDepth(root.right)
			return 1 + max(left, right)

		def getSubtrees(root):
			if root:
				leftDepth = getDepth(root.left)
				rightDepth = getDepth(root.right)
				if leftDepth == rightDepth:
					return root
				elif leftDepth > rightDepth:
					return getSubtrees(root.left)
				else:
					return getSubtrees(root.right)
		return getSubtrees(root)


class Solution:

	def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
		if not root:
			return root
		deepest = [[]]
		max_depth = [0]
		self.mark_depth_and_parent(root, deepest, max_depth)
		return self.get_lca(deepest[0])

	def mark_depth_and_parent(self, root, deepest, max_depth, depth=0, parent=None):
		if not root:
			return
		if depth > max_depth[0]:
			max_depth[0] = depth
			deepest[0] = [root]
		elif depth == max_depth[0]:
			deepest[0].append(root)
		root.depth = depth
		root.parent = parent
		self.mark_depth_and_parent(root.left, deepest, max_depth, depth + 1, root)
		self.mark_depth_and_parent(root.right, deepest, max_depth, depth + 1, root)

	def get_lca(self, deepest):
		while len(deepest) > 1:
			(n1, n2) = (deepest.pop(), deepest.pop())
			while n1 and n1.depth > n2.depth:
				n1 = n1.parent
			while n2 and n2.depth > n1.depth:
				n2 = n2.parent
			while n1 != n2:
				n1 = n1.parent
				n2 = n2.parent
			deepest.append(n1)
		return deepest[0]


class Solution:

	def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:

		def deep(node):
			if not node:
				return (0, None)
			ld = deep(node.left)
			rd = deep(node.right)
			if ld[0] > rd[0]:
				return (ld[0] + 1, ld[1])
			elif rd[0] > ld[0]:
				return (rd[0] + 1, rd[1])
			else:
				return (ld[0] + 1, node)
		return deep(root)[1]


class Solution:

	def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:

		def helper(node, depth):
			if not node:
				return (depth, None)
			(ld, ln) = helper(node.left, depth + 1)
			(rd, rn) = helper(node.right, depth + 1)
			if ld == rd:
				return (ld, node)
			if ld > rd:
				return (ld, ln)
			if ld < rd:
				return (rd, rn)
		(depth, res) = helper(root, 0)
		return res


class Solution:

	def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:

		def calcdeep(root, d, level):
			if level not in d:
				d[level] = []
			d[level].append(root)
			r1 = r2 = level
			if root.left != None:
				r1 = calcdeep(root.left, d, level + 1)
			if root.right != None:
				r2 = calcdeep(root.right, d, level + 1)
			return max(r1, r2)
		d = dict()
		maxl = calcdeep(root, d, 0)
		if len(d[maxl]) == 1:
			return d[maxl][0]

		def check2(root, ts, prefix, d):
			if root == None:
				return
			prefix.append(root)
			if root in ts:
				d[root.val] = copy.deepcopy(prefix)
			check2(root.left, ts, prefix, d)
			check2(root.right, ts, prefix, d)
			prefix.pop()
		targets = d[maxl]
		d = dict()
		prefix = []
		check2(root, targets, prefix, d)
		idx = maxl - 1
		while idx >= 0:
			vals = list(d.values())
			t = vals[0][idx]
			failed = False
			for val in list(d.values()):
				if val[idx].val != t.val:
					failed = True
					break
			if failed == False:
				return t
			idx -= 1
		return None