Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.
(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)
 
Example 1:

Input: [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: 
We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

 
Note:

The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

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 maxAncestorDiff(self, root: TreeNode) -> int:
        

Solutions:
class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.res = 0

		def helper(node, path_max, path_min):
			if not node:
				return 0
			path_max = max(path_max, node.val)
			path_min = min(path_min, node.val)
			self.res = max(self.res, path_max - path_min)
			helper(node.left, path_max, path_min)
			helper(node.right, path_max, path_min)
		if not root:
			return 0
		helper(root, root.val, root.val)
		return self.res


class Solution:
	answer = 0

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def dfs(node, max_v, min_v):
			self.answer = max(self.answer, abs(max_v - node.val))
			self.answer = max(self.answer, abs(min_v - node.val))
			if node.left:
				dfs(node.left, max(max_v, node.val), min(min_v, node.val))
			if node.right:
				dfs(node.right, max(max_v, node.val), min(min_v, node.val))
		dfs(root, root.val, root.val)
		return self.answer


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.res = 0

		def helper(node, max_val, min_val):
			if not node:
				self.res = max(self.res, max_val - min_val)
				return
			helper(node.left, max(max_val, node.val), min(min_val, node.val))
			helper(node.right, max(max_val, node.val), min(min_val, node.val))
		helper(root, 0, 100000)
		return self.res


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		return self.maxAncestorDiffHelper(root, [], 0)

	def maxAncestorDiffHelper(self, root: TreeNode, ancestors, maxV: int) -> int:
		if root is None:
			return 0
		for a in ancestors:
			maxV = max(maxV, abs(a - root.val))
		ancestors.append(root.val)
		maxV = max(maxV, self.maxAncestorDiffHelper(root.left, ancestors, maxV), self.maxAncestorDiffHelper(root.right, ancestors, maxV))
		ancestors.pop()
		return maxV


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		return self.helper(root, [], 0)

	def helper(self, root, anc, prevmax):
		if root == None:
			return prevmax
		real_prev = prevmax
		for a in anc:
			prevmax = max(prevmax, abs(a - root.val))
		anc.append(root.val)
		real_anc = list(anc)
		left = self.helper(root.left, anc, prevmax)
		right = self.helper(root.right, real_anc, prevmax)
		return max(left, right)


def maxDiff(root, arr):
	a = 0
	for i in arr:
		a = max(a, abs(i - root.val))
	b = 0
	c = 0
	if root.left:
		b = maxDiff(root.left, arr + [root.val])
	if root.right:
		c = maxDiff(root.right, arr + [root.val])
	return max(a, b, c)

class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		return maxDiff(root, [])


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def helper(root):
			if root == None:
				return []
			left = helper(root.left)
			right = helper(root.right)
			temp = []
			for i in range(len(left)):
				if abs(left[i] - root.val) > self.ans:
					self.ans = abs(left[i] - root.val)
				temp.append(left[i])
			for i in range(len(right)):
				if abs(right[i] - root.val) > self.ans:
					self.ans = abs(right[i] - root.val)
				temp.append(right[i])
			temp.append(root.val)
			return temp
		self.ans = 0
		helper(root)
		return self.ans


def findMaxDiff(node, collected):
	if not node:
		return float('-inf')
	cur_max = 0
	for v in collected:
		cur_max = max(cur_max, abs(v - node.val))
	left_max = findMaxDiff(node.left, collected + [node.val])
	right_max = findMaxDiff(node.right, collected + [node.val])
	return max(cur_max, left_max, right_max)

class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		return findMaxDiff(root, [])


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		maxel = -float('inf')

		def traverse(root, anc, maxel):
			if root:
				for i in anc:
					val = abs(i - root.val)
					maxel = max(maxel, val)
				anc.append(root.val)
				maxel = traverse(root.right, anc, maxel)
				maxel = traverse(root.left, anc, maxel)
				anc.pop(-1)
			return maxel
		return traverse(root, [], maxel)


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.ans = 0

		def preorder(root, minval, maxval):
			if not root:
				self.ans = max(self.ans, abs(minval - maxval))
				return
			preorder(root.left, min(minval, root.val), max(maxval, root.val))
			preorder(root.right, min(minval, root.val), max(maxval, root.val))
		preorder(root, float('inf'), float('-inf'))
		return self.ans


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		return self.helper(root)[1]

	def helper(self, root):
		if root == None:
			return (None, 0, None)
		elif root.left == None and root.right == None:
			return (root.val, 0, root.val)
		elif root.left == None:
			(r_low, r_long, r_high) = self.helper(root.right)
			return (min(r_low, root.val), max(r_long, abs(root.val - r_low), abs(root.val - r_high)), max(r_high, root.val))
		elif root.right == None:
			(l_low, l_long, l_high) = self.helper(root.left)
			return (min(l_low, root.val), max(l_long, abs(root.val - l_low), abs(root.val - l_high)), max(l_high, root.val))
		else:
			(r_low, r_long, r_high) = self.helper(root.right)
			(l_low, l_long, l_high) = self.helper(root.left)
			print(root, r_high, l_high, l_long, r_long)
			return (min(l_low, root.val, r_low), max(r_long, l_long, abs(root.val - min(l_low, r_low)), abs(root.val - max(r_high, l_high))), max(r_high, l_high, root.val))


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def recurse(node):
			if node is None:
				return (float('inf'), float('-inf'))
			else:
				(left_min, left_max) = recurse(node.left)
				(right_min, right_max) = recurse(node.right)
				current_min = min(left_min, right_min)
				current_max = max(left_max, right_max)
				val = node.val
				d = 0
				if current_min != float('inf'):
					d = max(d, abs(current_min - val))
				if current_max != float('-inf'):
					d = max(d, abs(current_max - val))
				self.maxDist = max(self.maxDist, d)
				return (min(current_min, val), max(current_max, val))
		self.maxDist = 0
		recurse(root)
		return self.maxDist


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.ans = 0

		def traverse(node, max_v, min_v):
			self.ans = max(self.ans, abs(max_v - min_v))
			_ = any((traverse(adj, max(max_v, adj.val), min(min_v, adj.val)) for adj in [node.left, node.right] if adj))
		traverse(root, root.val, root.val)
		return self.ans


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def findMaxDiff(node, max_sf, min_sf):
			if not node:
				return float('-inf')
			cur_max = max(abs(node.val - max_sf), abs(node.val - min_sf))
			(max_sf, min_sf) = (max(max_sf, node.val), min(min_sf, node.val))
			left_max = findMaxDiff(node.left, max_sf, min_sf)
			right_max = findMaxDiff(node.right, max_sf, min_sf)
			return max(cur_max, left_max, right_max)
		return findMaxDiff(root, root.val, root.val)


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def mdiff(root, maxval, minval):
			if not root:
				return -1
			maxval = max(root.val, maxval)
			minval = min(minval, root.val)
			return max(abs(maxval - minval), mdiff(root.left, maxval, minval), mdiff(root.right, maxval, minval))
		return mdiff(root, 0, 100000)


class Solution:

	def maxAncestorDiff(self, node: TreeNode) -> int:

		def helper(node, max_val, min_val):
			if not node:
				return 0
			diff = max(abs(max_val - node.val), abs(min_val - node.val))
			max_val = max(node.val, max_val)
			min_val = min(node.val, min_val)
			return max(helper(node.left, max_val, min_val), helper(node.right, max_val, min_val), diff)
		if not node:
			return 0
		return helper(node, node.val, node.val)


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def dfs(node, path):
			if node.left == None and node.right == None:
				if len(path) > 1:
					res[0] = max(res[0], abs(max(path) - min(path)))
				return
			else:
				if node.left:
					dfs(node.left, path + [node.left.val])
				if node.right:
					dfs(node.right, path + [node.right.val])
				return
		res = [-1 * float('infinity')]
		dfs(root, [root.val])
		return res[0]


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def dfs(root: TreeNode, path: List[int]) -> None:
			if root is None:
				return
			path = path + [root.val]
			if root.left is None and root.right is None:
				result.append(path)
			else:
				dfs(root.left, path)
				dfs(root.right, path)
		result = []
		dfs(root, path=[])
		return max([abs(max(arr) - min(arr)) for arr in result])


import numpy as np

class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		global_max = 0

		def dfs(t):
			if t is None:
				return []
			lim_span_l = dfs(t.left)
			lim_span_r = dfs(t.right)
			nonlocal global_max
			lim_span = [t.val]
			if lim_span_l:
				global_max = max(global_max, np.max(np.abs(t.val - np.array(lim_span_l))))
				lim_span.extend(lim_span_l)
			if lim_span_r:
				global_max = max(global_max, np.max(np.abs(t.val - np.array(lim_span_r))))
				lim_span.extend(lim_span_r)
			return [min(lim_span), max(lim_span)]
		intv = dfs(root)
		return global_max


from bisect import insort
from copy import copy

class Solution:

	def traverse(self, root, path=[]):
		if root is None:
			return
		path = copy(path)
		insort(path, root.val)
		if root.left is None and root.right is None:
			path_abs_diff = max(path) - min(path)
			self.max_abs_diff = max(self.max_abs_diff, path_abs_diff)
		self.traverse(root.left, path)
		self.traverse(root.right, path)

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.max_abs_diff = 0
		self.traverse(root)
		return self.max_abs_diff


class Solution:

	def traverse(self, root, path=[]):
		if root is None:
			return
		path = path + [root.val]
		if root.left is None and root.right is None:
			path_abs_diff = max(path) - min(path)
			self.max_abs_diff = max(self.max_abs_diff, path_abs_diff)
		elif root.left is None:
			self.traverse(root.right, path)
		elif root.right is None:
			self.traverse(root.left, path)
		else:
			self.traverse(root.left, path)
			self.traverse(root.right, path)

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.max_abs_diff = 0
		self.traverse(root)
		return self.max_abs_diff


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		return self.recursiveMax(root, root.val, root.val)

	def recursiveMax(self, root, largest, smallest):
		if root is None:
			return 0
		else:
			diff1 = abs(root.val - largest)
			diff2 = abs(root.val - smallest)
			largest = max(root.val, largest)
			smallest = min(root.val, smallest)
			return max(diff1, diff2, self.recursiveMax(root.left, largest, smallest), self.recursiveMax(root.right, largest, smallest))


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		paths = []

		def pathsToLeafs(root, comp):
			if not root:
				return
			if not root.left and (not root.right):
				paths.append(comp + [root.val])
				return
			pathsToLeafs(root.left, comp + [root.val])
			pathsToLeafs(root.right, comp + [root.val])
		pathsToLeafs(root, [])

		def maxDiff(a):
			val = 0
			n = len(a)
			dp = [0] * n
			for i in range(1, n):
				val = max(val + a[i] - a[i - 1], dp[i])
				dp[i] = max(val, dp[i - 1])
			return dp[-1]
		res = 0
		for path in paths:
			res = max(res, maxDiff(path), maxDiff(path[::-1]))
		return res


class Solution:

	def solve(self, lst, root):
		max_current = lst[-1][1]
		min_current = lst[-1][0]
		if root is not None:
			current_value = root.val
			if current_value > max_current:
				max_current = current_value
			if current_value < min_current:
				min_current = current_value
			lst.append((min_current, max_current))
			return max(self.solve(lst[:], root.left), self.solve(lst[:], root.right))
		else:
			max_val = max_current - min_current
			return max_val

	def maxAncestorDiff(self, root: TreeNode) -> int:
		lst = [(root.val, root.val)]
		return max(self.solve(lst[:], root.left), self.solve(lst[:], root.right))


LEFT_PROCESSED = 1
RIGHT_PROCESSED = 2

class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def recurse_func(node, parent_vals, best_answer):
			if parent_vals:
				ans = abs(min(parent_vals) - node.val)
				if ans > best_answer:
					best_answer = ans
				ans = abs(max(parent_vals) - node.val)
				if ans > best_answer:
					best_answer = ans
			parent_vals.append(node.val)
			if node.left:
				best_answer = recurse_func(node.left, parent_vals, best_answer)
			if node.right:
				best_answer = recurse_func(node.right, parent_vals, best_answer)
			parent_vals.pop()
			return best_answer
		return recurse_func(root, [], 0)


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.v_max = 0

		def find(node, path):
			if not node:
				return
			tmp = max(abs(max(path) - node.val), abs(min(path) - node.val))
			self.v_max = max(self.v_max, tmp)
			path.append(node.val)
			find(node.left, path)
			find(node.right, path)
			path.pop()
		find(root, [root.val])
		return self.v_max


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		if not root:
			return 0
		stack = [(root, root.val, root.val)]
		maxDiff = -1
		while stack:
			(node, maxVal, minVal) = stack.pop()
			maxVal = max(maxVal, node.val)
			minVal = min(minVal, node.val)
			maxDiff = max(maxDiff, maxVal - minVal)
			if node.left:
				stack.append((node.left, maxVal, minVal))
			if node.right:
				stack.append((node.right, maxVal, minVal))
		return maxDiff


class Solution:
	maxDiff = 0

	def maxAncestorDiff(self, root: TreeNode) -> int:
		if not root:
			return 0
		currPath = []

		def dfs(currNode, currPath):
			currPath.append(currNode.val)
			if currNode.left:
				dfs(currNode.left, currPath)
			if currNode.right:
				dfs(currNode.right, currPath)
			self.maxDiff = max(self.maxDiff, max(currPath) - min(currPath))
			currPath.pop()
		dfs(root, currPath)
		return self.maxDiff


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.mx = 0
		path = []

		def getpath(root):
			if not root:
				return
			path.append(root.val)
			if len(path) > 1:
				self.mx = max(self.mx, abs(min(path[:-1]) - path[-1]))
				self.mx = max(self.mx, abs(max(path[:-1]) - path[-1]))
			getpath(root.left)
			getpath(root.right)
			path.pop()
		getpath(root)
		return self.mx


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.max_diff = -float('inf')
		self.dfs(root, [])
		return self.max_diff

	def dfs(self, root, path):
		if not root:
			self.max_diff = max(self.max_diff, max(path) - min(path))
			return
		self.dfs(root.left, path + [root.val])
		self.dfs(root.right, path + [root.val])


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.maxval = float('-inf')

		def dfs(node, ans):
			if node:
				if ans:
					self.maxval = max(self.maxval, abs(max(ans) - node.val))
					self.maxval = max(self.maxval, abs(min(ans) - node.val))
				dfs(node.left, ans + [node.val])
				dfs(node.right, ans + [node.val])
		dfs(root, [])
		return self.maxval


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def traverse(root, prev_min, prev_max):
			if root:
				prev_min = min(root.val, prev_min)
				prev_max = max(root.val, prev_max)
				return max(traverse(root.left, prev_min, prev_max), traverse(root.right, prev_min, prev_max))
			else:
				return prev_max - prev_min
		return traverse(root, root.val, root.val)


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.max_diff = -float('inf')

		def helper(node, vals):
			if not node:
				self.max_diff = max(self.max_diff, abs(max(vals) - min(vals)))
				return
			helper(node.left, vals + [node.val])
			helper(node.right, vals + [node.val])
		helper(root, [root.val])
		return self.max_diff


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.dist = 0

		def dfs(node, ancesVal):
			if not node:
				self.dist = max(self.dist, abs(max(ancesVal) - min(ancesVal)))
				return
			dfs(node.left, ancesVal + [node.val])
			dfs(node.right, ancesVal + [node.val])
			return
		dfs(root, [])
		return self.dist


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		stack = [[root, [root.val]]]
		res = 0
		while stack:
			(node, ancestors) = stack[0]
			res = max(res, abs(node.val - ancestors[0]), abs(node.val - ancestors[-1]))
			for i in range(len(ancestors)):
				if node.val >= ancestors[i]:
					new_ancestors = ancestors[0:i] + [node.val] + ancestors[i:]
					break
				if i == len(ancestors) - 1:
					new_ancestors = ancestors + [node.val]
			if node.left != None:
				stack.append([node.left, new_ancestors])
			if node.right != None:
				stack.append([node.right, new_ancestors])
			stack = stack[1:]
		return res


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		maxDiff = 0
		stk = [root]
		ancDict = {}
		ancDict[root.val] = []
		while len(stk) != 0:
			root = stk.pop()
			if root.left is not None:
				stk.append(root.left)
				if root.left not in ancDict:
					ancDict[root.left.val] = []
				ancDict[root.left.val].append(root.val)
				ancDict[root.left.val].extend(ancDict[root.val])
			if root.right is not None:
				stk.append(root.right)
				if root.right not in ancDict:
					ancDict[root.right.val] = []
				ancDict[root.right.val].append(root.val)
				ancDict[root.right.val].extend(ancDict[root.val])
		for k in ancDict:
			for v in ancDict[k]:
				if abs(v - k) > maxDiff:
					maxDiff = abs(v - k)
		return maxDiff


import queue
from collections import defaultdict

class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		maxDiff = 0
		dq = queue.deque()
		dq.append(root)
		data = []
		nodes = defaultdict(list)
		while any(dq):
			node = dq.popleft()
			data.append(node.val)
			if node.left:
				dq.append(node.left)
				nodes[node.left.val].append(node.val)
				nodes[node.left.val].extend(nodes[node.val])
			if node.right:
				dq.append(node.right)
				nodes[node.right.val].append(node.val)
				nodes[node.right.val].extend(nodes[node.val])
		for (key, value) in list(nodes.items()):
			if not value:
				continue
			s = 0
			for val in value:
				if abs(key - val) > s:
					s = abs(key - val)
			if s > maxDiff:
				maxDiff = s
		return maxDiff


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.ans = -1

		def solve(r: TreeNode, ancestors: List[int]):
			if r is None:
				return
			v = r.val
			if len(ancestors) > 0:
				tmp = max([abs(a - v) for a in ancestors])
				self.ans = max(tmp, self.ans)
			ancestors.append(v)
			solve(r.left, ancestors)
			solve(r.right, ancestors)
			ancestors.pop()
		solve(root, [])
		return self.ans


def calculateDifference(root, parent):
	maxi = 0
	for i in parent:
		if abs(root.val - i) > maxi:
			maxi = abs(root.val - i)
	if root.left:
		maxi = max(maxi, calculateDifference(root.left, parent + [root.val]))
	if root.right:
		maxi = max(maxi, calculateDifference(root.right, parent + [root.val]))
	return maxi

class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		if root is None:
			return 0
		return calculateDifference(root, [])


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def recAncestors(root, ancestors, dif):
			left_dif = 0
			right_dif = 0
			for node in ancestors:
				if dif < abs(root.val - node):
					dif = abs(root.val - node)
			father = ancestors + [root.val]
			if root.left:
				left_dif = recAncestors(root.left, father, dif)
			if root.right:
				right_dif = recAncestors(root.right, father, dif)
			return max(left_dif, right_dif, dif)
		nodes = [root.val]
		(right_wing, left_wing) = (0, 0)
		if root.right:
			right_wing = recAncestors(root.right, nodes, 0)
		if root.left:
			left_wing = recAncestors(root.left, nodes, 0)
		return max(right_wing, left_wing)


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def recurse_func(node, parent_vals, best_answer):
			for x in parent_vals:
				ans = abs(x - node.val)
				if ans > best_answer:
					best_answer = ans
			parent_vals.append(node.val)
			if node.left:
				best_answer = recurse_func(node.left, parent_vals, best_answer)
			if node.right:
				best_answer = recurse_func(node.right, parent_vals, best_answer)
			parent_vals.pop()
			return best_answer
		return recurse_func(root, [], 0)


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def traverse(root, anc, diff):
			if root:
				for an in anc:
					if abs(root.val - an) > diff:
						diff = abs(root.val - an)
				diff = traverse(root.left, anc + [root.val], diff)
				diff = traverse(root.right, anc + [root.val], diff)
			return diff
		return traverse(root, [], 0)


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def maxDiff(root, ancestors):
			if root is None:
				return 0
			maxRightHere = 0
			for ancestor in ancestors:
				difference = abs(ancestor - root.val)
				if difference > maxRightHere:
					maxRightHere = difference
			ancestors.append(root.val)
			maxLeft = maxDiff(root.left, ancestors)
			maxRight = maxDiff(root.right, ancestors)
			ancestors.pop()
			return max(maxRightHere, maxLeft, maxRight)
		return maxDiff(root, [])


from dataclasses import dataclass
MIN_VALUE = -2 ** 31
MAX_VALUE = 2 ** 31

@dataclass
class State:
	min_: int
	max_: int
	val: int

def max_ancestor_diff(root: TreeNode) -> State:
	if not root:
		return State(MAX_VALUE, MIN_VALUE, 0)
	left = max_ancestor_diff(root.left)
	right = max_ancestor_diff(root.right)
	min_ = min(left.min_, right.min_, root.val)
	max_ = max(left.max_, right.max_, root.val)
	val = max(left.val, right.val, max_ - root.val, root.val - min_)
	return State(min_, max_, val)

class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		return max_ancestor_diff(root).val


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		if not root:
			return 0
		maxDiff = 0

		def dfs(node):
			if not node:
				return []
			vals = dfs(node.left)
			vals.extend(dfs(node.right))
			nonlocal maxDiff
			localMaxDiff = max([abs(v - node.val) for v in vals]) if vals else 0
			maxDiff = max(maxDiff, localMaxDiff)
			vals.append(node.val)
			return vals
		dfs(root)
		return maxDiff


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		stack = [(root, [])]
		maxDiff = 0
		while stack:
			(node, anc) = stack.pop()
			if anc:
				maxDiff = max(maxDiff, max((abs(node.val - v) for v in anc)))
			if node.left:
				stack.append((node.left, anc + [node.val]))
			if node.right:
				stack.append((node.right, anc + [node.val]))
		return maxDiff


class Solution:

	def helper(self, root, output, maxValue):
		if root is None:
			return
		for ele in output:
			if abs(root.val - ele) > maxValue[0]:
				maxValue[0] = abs(root.val - ele)
		output.append(root.val)
		self.helper(root.left, output, maxValue)
		self.helper(root.right, output, maxValue)
		output.pop()

	def maxAncestorDiff(self, root: TreeNode) -> int:
		maxValue = [0]
		output = list()
		self.helper(root, output, maxValue)
		return maxValue[0]


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def dfs(node, path):
			if node.left == None and node.right == None:
				res[0] = max(res[0], max([abs(j - node.val) for j in path]))
				return
			else:
				if len(path) > 0:
					res[0] = max(res[0], max([abs(j - node.val) for j in path]))
				if node.left:
					dfs(node.left, path + [node.val])
				if node.right:
					dfs(node.right, path + [node.val])
				return
		res = [-1 * float('infinity')]
		dfs(root, [])
		print(res)
		return res[0]


class Solution:

	def __init__(self):
		self.max_diff = -1

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def max_diff_calc(root):
			if not root:
				return []
			ancestors = max_diff_calc(root.left)
			ancestors.extend(max_diff_calc(root.right))
			for ans in ancestors:
				if abs(root.val - ans) > self.max_diff:
					self.max_diff = abs(root.val - ans)
			ancestors.append(root.val)
			return ancestors
		max_diff_calc(root)
		return self.max_diff


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		res = 0
		if not root:
			return

		def dfs(node, a):
			nonlocal res
			tmp = max((abs(x - node.val) for x in a)) if a else 0
			res = max(res, tmp)
			if node.left:
				a.append(node.left.val)
				dfs(node.left, a)
				a.pop()
			if node.right:
				a.append(node.right.val)
				dfs(node.right, a)
				a.pop()
			return
		dfs(root, [root.val])
		return res


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def tranverse(node, ansestors, res):
			res = max(res, max([abs(val - node.val) for val in ansestors]) if ansestors else 0)
			ansestors.append(node.val)
			if node.left:
				res = tranverse(node.left, ansestors, res)
			if node.right:
				res = tranverse(node.right, ansestors, res)
			ansestors.pop()
			return res
		return tranverse(root, [], 0)


class Solution:

	def helper(self, root, path, ans):
		if not root:
			return
		if path:
			ans[0] = max(ans[0], max([abs(root.val - x) for x in path]))
		path.append(root.val)
		self.helper(root.left, path.copy(), ans)
		self.helper(root.right, path.copy(), ans)

	def maxAncestorDiff(self, root: TreeNode) -> int:
		ans = [-float('inf')]
		self.helper(root, [], ans)
		return ans[0]


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		return self.helper(root)[1]

	def helper(self, root, myMax=0):
		myList = []
		if root.left:
			(temp1, temp2) = self.helper(root.left)
			myList.extend(temp1)
			if temp2 > myMax:
				myMax = temp2
		if root.right:
			(temp1, temp2) = self.helper(root.right)
			myList.extend(temp1)
			if temp2 > myMax:
				myMax = temp2
		myList.append(root.val)
		for i in range(len(myList) - 1):
			if abs(root.val - myList[i]) > myMax:
				myMax = abs(root.val - myList[i])
		return (myList, myMax)


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		best = {0: -1}

		def maxmin(root, path):
			if root == None:
				return 200000
			else:
				best[0] = max(best[0], max([0] + [abs(root.val - val) for val in path]))
				maxmin(root.left, path + [root.val])
				maxmin(root.right, path + [root.val])
		maxmin(root, [])
		return best[0]


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		if not root or (not root.left and (not root.right)):
			return 0
		self.max_val = 0
		self.traverseWithAncestor(root, [])
		return self.max_val

	def traverseWithAncestor(self, root, ancestors):
		if not root:
			return
		for v in ancestors:
			if (res := abs(root.val - v)) > self.max_val:
				self.max_val = res
		if not root.left and (not root.right):
			return
		newAncestors = list(ancestors)
		newAncestors.append(root.val)
		if root.left:
			self.traverseWithAncestor(root.left, newAncestors)
		if root.right:
			self.traverseWithAncestor(root.right, newAncestors)


class Solution:
	abs_max = -99999

	def construct_all_pairs(self, subtree):
		if subtree is None:
			return []
		else:
			lp = self.construct_all_pairs(subtree.left)
			rp = self.construct_all_pairs(subtree.right)
			for l in lp:
				if abs(subtree.val - l) > self.abs_max:
					self.abs_max = abs(subtree.val - l)
			for r in rp:
				if abs(subtree.val - r) > self.abs_max:
					self.abs_max = abs(subtree.val - r)
			return [subtree.val] + lp + rp

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.construct_all_pairs(root)
		return self.abs_max


class Solution:
	ans = 0

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def visit(root, ancs):
			if root is None:
				return
			if ancs:
				self.ans = max(self.ans, max((abs(root.val - o) for o in ancs)))
			visit(root.left, ancs + [root.val])
			visit(root.right, ancs + [root.val])
		visit(root, [])
		return self.ans


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		if not root:
			return 0

		def maxDiff(root: TreeNode, ancestors: List[int]) -> int:
			if not root:
				return 0
			left_max = maxDiff(root.left, ancestors + [root.val])
			right_max = maxDiff(root.right, ancestors + [root.val])
			diffs = [abs(ancestor - root.val) for ancestor in ancestors]
			return max(diffs + [left_max, right_max])
		return maxDiff(root, [])


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.mx = 0

		def dfs(node, visited):
			if node is None:
				return
			else:
				for v in visited:
					if abs(v - node.val) > self.mx:
						self.mx = abs(v - node.val)
			dfs(node.left, visited + [node.val])
			dfs(node.right, visited + [node.val])
			return
		dfs(root, [])
		return self.mx


class Solution:

	def dfs(self, root, ancestors):
		if ancestors:
			for anc in ancestors:
				potential = abs(root.val - anc)
				if potential > self.ans:
					self.ans = potential
		if root.left:
			self.dfs(root.left, ancestors + [root.val])
		if root.right:
			self.dfs(root.right, ancestors + [root.val])

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.ans = 0
		self.dfs(root, [])
		return self.ans


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.max_val = 0

		def traversal(root, parent):
			if not root:
				return
			for i in parent:
				if self.max_val < abs(i - root.val):
					self.max_val = abs(i - root.val)
			if root.left:
				traversal(root.left, parent + [root.val])
			if root.right:
				traversal(root.right, parent + [root.val])
			return
		traversal(root, [])
		return self.max_val


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.max_d = 0

		def get_distance_list(node, dist_list):
			dist_list_new = []
			if not (node.left or node.right):
				return [0]
			else:
				if node.left:
					dist_list_l = get_distance_list(node.left, dist_list)
					diff_l = node.val - node.left.val
					dist_list_l = [d + diff_l for d in dist_list_l]
					dist_list_new += dist_list_l
					dist_list_new.append(diff_l)
				if node.right:
					dist_list_r = get_distance_list(node.right, dist_list)
					diff_r = node.val - node.right.val
					dist_list_r = [d + diff_r for d in dist_list_r]
					dist_list_new += dist_list_r
					dist_list_new.append(diff_r)
			for d in dist_list_new:
				if abs(d) > self.max_d:
					self.max_d = abs(d)
			return dist_list_new
		get_distance_list(root, [])
		return self.max_d


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		self.max_p_diff = 0

		def max_diff(node, p_min, p_max):
			if not node:
				return
			self.max_p_diff = max(self.max_p_diff, max(abs(node.val - p_min), abs(p_max - node.val)))
			p_min = min(node.val, p_min)
			p_max = max(node.val, p_max)
			max_diff(node.left, p_min, p_max)
			max_diff(node.right, p_min, p_max)
		max_diff(root, root.val, root.val)
		return self.max_p_diff


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def util(root, maxDiff):
			if not root:
				return ([], maxDiff)
			(lArr, maxDiff) = util(root.left, maxDiff)
			(rArr, maxDiff) = util(root.right, maxDiff)
			for node in lArr:
				if abs(root.val - node.val) > maxDiff:
					maxDiff = abs(root.val - node.val)
			for node in rArr:
				if abs(root.val - node.val) > maxDiff:
					maxDiff = abs(root.val - node.val)
			return ([root] + lArr + rArr, maxDiff)
		(arr, maxDiff) = util(root, float('-inf'))
		return maxDiff


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:

		def dfs(root: TreeNode, ancestors_values) -> int:
			result = [-1]
			this_ancestors_values = [root.val] + ancestors_values
			if root.left is not None:
				max_ancestors_diff = max([abs(a - root.left.val) for a in this_ancestors_values])
				left_result = dfs(root.left, this_ancestors_values)
				left_result = max(left_result, max_ancestors_diff)
				result.append(left_result)
			if root.right is not None:
				max_ancestors_diff = max([abs(a - root.right.val) for a in this_ancestors_values])
				right_result = dfs(root.right, this_ancestors_values)
				right_result = max(right_result, max_ancestors_diff)
				result.append(right_result)
			return max(result)
		result = dfs(root, [])
		return result


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		if not root:
			return 0
		stack = [root]
		parent = {root: None}
		while stack:
			p = stack.pop()
			if p.right:
				stack.append(p.right)
				parent[p.right] = p
			if p.left:
				stack.append(p.left)
				parent[p.left] = p
		ans = 0
		for nodes in parent:
			res = []
			while nodes:
				res.append(nodes.val)
				nodes = parent[nodes]
			ans = max(ans, max(res) - min(res))
		return ans


from typing import List

class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		return max_ancestor_diff(root, [])

def max_ancestor_diff(node: TreeNode, lineage: List[TreeNode]) -> int:
	if node is None:
		return 0
	if lineage:
		max_diff = max([abs(node.val - n.val) for n in lineage])
	else:
		max_diff = 0
	if node.left is not None:
		max_diff = max(max_diff, max_ancestor_diff(node.left, lineage + [node]))
	if node.right is not None:
		max_diff = max(max_diff, max_ancestor_diff(node.right, lineage + [node]))
	return max_diff


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		deque = collections.deque([[root, []]])
		result = 0
		while deque:
			(node, anc) = deque.popleft()
			max_abs = 0 if not len(anc) else max((abs(node.val - a.val) for a in anc))
			result = max(result, max_abs)
			if node.left:
				deque.append([node.left, anc + [node]])
			if node.right:
				deque.append([node.right, anc + [node]])
		return result


class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		q = [(root, [])]
		from collections import defaultdict
		anc = {}
		while q:
			(cur, path) = q.pop(0)
			anc[cur.val] = path
			path.append(cur.val)
			if cur.left:
				q.append((cur.left, path[:]))
			if cur.right:
				q.append((cur.right, path[:]))
		max_diff = float('-inf')
		for (n, ancs) in list(anc.items()):
			for a in ancs:
				max_diff = max(max_diff, abs(a - n))
		return max_diff


from typing import List
from functools import lru_cache

class TreeNode:

	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

	def __repr__(self):
		return str(self.val)

class Solution:

	def maxAncestorDiff(self, root: TreeNode) -> int:
		return max_ancestor_diff(root, [])

@lru_cache
def get_max_lineage_diff(node: TreeNode, lineage) -> int:
	if lineage:
		return max([abs(node.val - n.val) for n in lineage])
	else:
		return 0

def max_ancestor_diff(node: TreeNode, lineage: List[TreeNode]) -> int:
	if node is None:
		return 0
	max_diff = get_max_lineage_diff(node, frozenset(lineage))
	if node.left is not None:
		max_diff = max(max_diff, max_ancestor_diff(node.left, lineage + [node]))
	if node.right is not None:
		max_diff = max(max_diff, max_ancestor_diff(node.right, lineage + [node]))
	return max_diff