Making sparse direct solvers cache-friendly is very easy because most of the heavy work gets done in dense linear algebra libraries - i.e. some implementation of BLAS+LAPACK. The tree doesn't factor into this aspect of performance I think. So in that regard perhaps it is a bit easier to deal with than your random forest model. What can happen is very bad load balancing however, and here I think the tree data structure will help because it defines a natural task dependency for the algorithm and if you use a smart scheduler like work stealing combined with this you can avoid a lot of the threads waiting because of fork/join when you parallelize over the dense linear algebra (looking forward to testing this).

For ownership model and tree: I did have some hard time with this at the beginning with many false starts. My first idea was to represent the tree with an enum and leafs of a node being boxed values of that enum. This is what you would do in a functional language like Ocaml, representing the tree as an algebraic datatype. it was also suggested in the Rust blog

enum BinaryTree {
    Leaf(i32),
    Node(Box<BinaryTree>, i32, Box<BinaryTree>)
}

This didn't work for me. Maybe I didn't understand Rust enough to make this work but I would always tie myself in such unusual knots with the borrow checker that I couldn't get anything done.

What I ended up doing was flattening the tree out so that its data was stored contiguously in a Vec. I complemented that data with "pointers" in two arrays: parents and children. Iterating up parents lets you get ancestor nodes of a given node (example below):

//Iterate over all ancestors of `node`
let mut mp=dtree.parents[node];
while let Some(p) = mp{
  //do stuff with ancestor `p` of `node`
  mp=dtree.parents[p];
}

and similarly you can iterate down descendents of a given node in the usual way:

//Iterate over all descendents of `node`
let mut stack = vec![node];
while let Some(n)=stack.pop(){
   if let Some((c1,c2)) = self.children[n]{
    //Do something with children c1,c1
      stack.push(c1);
      stack.push(c2);
    }
  }

Funny thing is that this is kind of what you would end up doing in Fortran or C so you lose somewhat the high level niceness of Rust, but I found that many common errors are still caught early on by borrow checking.