< Back





1026. Maximum Difference Between Node and Ancestor

We're given the root of a binary tree and asked to find the maximum difference between two nodes on
any path in the tree starting from the root. So the path can't be from the left side of the root to
the other side of the tree - it has to be between an ancestor and a descendant.

Given this, we can conduct depth-first search to search paths in the tree. At each node during the
search, we need to maintain the maximum value seen so far as well as the minimum. We also update the
global answer variable with max difference between the current node and the known maximum and
minimum.

After conducting this maintainence at each node, we pass the maximum and minimum value to the left
and right descendants. We continue this process until we reach the leaves of the tree.

The solution is as follows:


  class Solution:
      def __init__(self):
          self.ans = float("-inf")

      def dfs(self, node: Optional[TreeNode], maxVal: int, minVal: int) -> None:
          if not node:
              return

          self.ans = max(self.ans, abs(maxVal - node.val), abs(minVal - node.val))
          maxVal = max(maxVal, node.val)
          minVal = min(minVal, node.val)

          self.dfs(node.left, maxVal, minVal)
          self.dfs(node.right, maxVal, minVal)

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


_ Time Complexity:

  O(n) - We inspect all nodes in the binary tree.

_ Space Complexity:

  O(n) - Our call stack can grow to the size of the number of nodes in the tree.