struct Node { key: i32, count: i32, left: Option<usize>, right: Option<usize> }
fn insert(pool: &mut Vec<Node>, key: i32) {
    if pool.is_empty() {
        pool.push(Node { key, count: 1, left: None, right: None });
        return;
    }
    let mut cur = 0;
    loop {
        if key == pool[cur].key { pool[cur].count += 1; return; }
        let left = key < pool[cur].key;
        let child = if left { pool[cur].left } else { pool[cur].right };
        if let Some(next) = child { cur = next; continue; }
        let next = pool.len();
        pool.push(Node { key, count: 1, left: None, right: None });
        if left { pool[cur].left = Some(next); } else { pool[cur].right = Some(next); }
        return;
    }
}

fn main() {
    let mut pool=vec![];
    for key in [5,3,7,3,1,9] { insert(&mut pool,key); }
    assert_eq!(pool.len(),5);let left=pool[0].left.unwrap();assert_eq!((pool[left].key,pool[left].count),(3,2));
    assert_eq!(pool[pool[0].right.unwrap()].key,7);
}