09 Nov 2020
Maximum difference between node and ancestor
Source: https://leetcode.com/problems/maximum-difference-between-node-and-ancestorTags: binary tree, recursion
Problem
Given the root of a binary tree, find the maximum value
Vfor which there exist different nodesAandBwhereV = |A.val - B.val|andAis an ancestor ofB.A node
Ais an ancestor ofBif either: any child ofAis equal toB, or any child ofAis an ancestor ofB.
Some questions to ask
- What to do for a singleton tree?
- Is the tree a binary search tree (BST)?
- For BST, simply take
max(abs(leftMost - root), abs(rightMost - root))
- For BST, simply take
Approach
A naive approach would be to traverse the tree using DFS and, for each node, compute all ancestor differences and pick the maximum.
As the question only concerns with the maximum ancestor difference, it suffices to only keep track of the extreme ancestor values (i.e. maximum and minimum), and compute the differences with these two ancestors at each node.
def maxAncestorDiff(node: TreeNode,
maxAncestor: Optional[int] = None,
minAncestor: Optional[int] = None) -> int:
"""Return maximum difference between any node rooted in
`tree` and its ancestors, given the encountered
`maxAncestor` and `minAncestor`."""
if node is None:
return 0
if maxAncestor is not None and minAncestor is not None:
# Compute maximum ancestor difference
# for current node w.r.t. its ancestors
currDiff = max(abs(node.val - maxAncestor),
abs(node.val - minAncestor))
else:
currDiff = 0
# Update (max|min) ancestors for children
if maxAncestor is None or node.val > maxAncestor:
maxAncestor = node.val
if minAncestor is None or node.val < minAncestor:
minAncestor = node.val
maxDiffLeftChild = maxAncestorDiff(node.left,
maxAncestor,
minAncestor)
maxDiffRightChild = maxAncestorDiff(node.right,
maxAncestor,
minAncestor)
# Reduce maximum ancestor difference
# as found from children
return max(currDiff, maxDiffLeftChild, maxDiffRightChild)
Complexity
Let n be the number of nodes in the tree.
- O(n) time complexity, for visiting each node exactly once
- O(1) space complexity, if ignoring the recursion overhead