Binary tree longest consecutive sequence

Tree Depth-First Search Binary Tree

54.7% acceptance

Mar 31, 2026

1183

239

Given the root of a binary tree, return the length of the longest consecutive sequence path. A consecutive sequence path is a path where the values increase by one along the path. Note that the path can start at any node in the tree, and you cannot go from a node to its parent in the path.

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 longest_consecutive(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut max_len = 0;
    Self::dfs(&root, None, 0, &mut max_len);
    max_len
  }

  fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, parent_val: Option<i32>, len: i32, max_len: &mut i32) {
    if let Some(n) = node {
      let val = n.borrow().val;
      let cur_len = if parent_val.is_some() && val == parent_val.unwrap() + 1 {
        len + 1
      } else {
        1
      };
      if cur_len > *max_len { *max_len = cur_len; }
      Self::dfs(&n.borrow().left, Some(val), cur_len, max_len);
      Self::dfs(&n.borrow().right, Some(val), cur_len, max_len);
    }
  }
}