Maximum difference between node and ancestor

Tree Depth-First Search Binary Tree

78.1% acceptance

Feb 27, 2026

5092

171

Given the root of a binary tree, find the maximum value v for which there exist 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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn max_ancestor_diff(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, mn: i32, mx: i32) -> i32 {
      if let Some(n) = node {
        let val = n.borrow().val;
        let mn2 = mn.min(val); let mx2 = mx.max(val);
        let l = n.borrow().left.clone();
        let r = n.borrow().right.clone();
        if l.is_none() && r.is_none() { return mx2 - mn2; }
        dfs(&l, mn2, mx2).max(dfs(&r, mn2, mx2))
      } else { 0 }
    }
    let v = root.as_ref().unwrap().borrow().val;
    dfs(&root, v, v)
  }
}