Решение задачи №80 от UniLecs, обобщённое на любой тип, для которого определена операция сравнения

path_in_bst_generic.rs

#![feature(slice_patterns)]

fn same_relation<Elem: Ord>(pivot: Elem, arr: &[Elem]) -> bool {
    match *arr {
        [] => true,
        [ref _single] => true,
        [ref first, ref rest..] =>  {
            let relation = pivot.cmp(first);
            rest.iter().all(|x| pivot.cmp(x) == relation)
        },
    }
}

fn can_be_path_in_bst<Elem: Ord + Clone>(arr: &[Elem]) -> bool {
    for i in 0..arr.len() {
        match arr[i..] {
            [] => return true,
            [ref _single] => return true,
            [ref first, ref rest..] =>
                if !same_relation(first.clone(), rest) { return false },
        }
    }
    true
}

fn can_be_path_in_bst2<Elem: Ord + Clone>(arr: &[Elem]) -> bool {
    match *arr {
        [] => true,
        [ref _single] => true,
        [ref first, ref rest..] => {
            use std::cmp::Ordering;
            
            let (mut lower, mut upper) = (None, None);
            let mut prev = first;
            
            for curr in rest {
                if lower.map(|lo| curr.cmp(lo) == Ordering::Less).unwrap_or(false)
                    || upper.map(|up| curr.cmp(up) == Ordering::Greater).unwrap_or(false) {
                    return false;
                }
                match curr.cmp(&prev) {
                    Ordering::Less => upper = Some(prev),
                    Ordering::Equal => (),
                    Ordering::Greater => lower = Some(prev),
                };
                prev = curr;
            }
            
            true
        },
    }
}

Все тесты для необобщённого варианта (кроме пустого массива, где требуется добавлять аннотацию типа), работают и для этого варианта: https://play.rust-lang.org/?gist=6f2e1b4fa18217c6133690d7448fb9d2&version=nightly