LCA practice

main.rs

#![feature(box_syntax)]

use Tree::{Leaf, Node};

#[derive(Debug)]
pub enum Tree<T> {
  Leaf,
  Node(Box<Tree<T>>, Box<Tree<T>>, T)
} 

impl<T> Tree<T> {
  pub fn val(&self) -> Option<&T> {
    match self {
      &Leaf => None,
      &Node(_, _, ref v) => Some(v)
    }
  }
}

impl<T> Tree<T> where T : PartialEq {
  pub fn lca(&self, el0: &T, el1: &T) -> Option<&Tree<T>> {
    match self._lca(el0, el1) {
      (2, Some(ref n)) => Some(n),
      _ => None 
    }
  }

  fn _lca(&self, el0: &T, el1: &T) -> (usize, Option<&Tree<T>>) {
    match self {
      &Leaf => (0, None),
      // Handles the case where `el0 == el1`
      &Node(_, _, ref el) if el == el0 && el == el1 => (2, None),
      // Handles the case where either `el == el0` or `el == el1`. 
      // Elements could be in the same subtree.
      &Node(ref lt, ref rt, ref el) if el == el0 || el == el1 => {
        let _lt = lt._lca(el0, el1);
        let _rt = rt._lca(el0, el1);

        (1 + _lt.0 + _rt.0, None)
      }
      // Handles the case where the node could be a parent
      &Node(ref lt, ref rt, _) => {
        let _lt = lt._lca(el0, el1);
        let _rt = rt._lca(el0, el1);
        let lca = _lt.0 == 1 && _rt.0 == 1 || 
          match _lt { (2, None) => true, _ => false } || 
          match _rt { (2, None) => true, _ => false }; 

        if lca {
          (2, Some(&self))
        } else if _lt.0 == 2 {
          _lt
        } else if _rt.0 == 2 {
          _rt
        } else {
          (_lt.0 + _rt.0, Some(&self))
        }
      }
    }
  }
}

//              F
//             / \
//     B                  G
//    / \                  \
//   A  D                  I
//     / \                /
//    C  E               H
#[cfg(test)] #[test]
fn test_lca() {
  let tree = Node(
    box Node(
      box Node(
        box Leaf,
        box Leaf,
        'A'),
      box Node(
        box Node(
          box Leaf,
          box Leaf,
          'C'),
        box Node(
          box Leaf,
          box Leaf,
          'E'),
        'D'),
      'B'),
    box Node(
      box Leaf,
      box Node(
        box Node(
          box Leaf,
          box Leaf,
          'H'),
        box Leaf,
        'I'),
      'G'),
    'F');

  macro_rules! test_lca {
    ($expected : expr, $el0 : expr, $el1 : expr) => {
        assert_eq!(tree.lca(&$el0, &$el1).unwrap().val().unwrap_or(&'X'), &$expected);
    }
  }

  test_lca!('D', 'C', 'E');
  test_lca!('F', 'H', 'B');
  test_lca!('B', 'C', 'A');
  test_lca!('F', 'B', 'B');
  test_lca!('G', 'H', 'I');

  assert!(tree.lca(&'X', &'Y').is_none());
}