.

1
2
3
4
5
6
7
8
relabel::Tree -> Tree
relabel t = let (t', size) = re (t, size) in t'
re :: (Tree, Int) -> (Tree, Int)
re (Leaf x, s) = (Leaf (if x < s then (2*s) else x) , 1)
re (Node l x r, s) =
    let (l', sl) = re (l,s)
        (r', sr) = re (r, s)
      in (Node l' (if x < s then (2*s) else x)  r', (1+sr+sl))