unknown-tree.hs

data Digit a = One !a | Two !a !a

data Tree a = Nil | Tree (Digit a) (Tree a) (Tree a)

cons :: a -> Tree a -> Tree a -- O(1)
cons a Nil = Tree (One a) Nil Nil
cons a (Tree (One b) xs ys) = Tree (Two a b) xs ys
cons a (Tree (Two b c) xs ys) = Tree (One a) (cons b xs) (cons c ys)

index :: Int -> Tree a -> Maybe a -- O(log n)
index _ Nil = Nothing
index 0 (Tree (One a) _ _) = Just a
index 0 (Tree (Two a _) _ _) = Just a
index 1 (Tree (Two _ b) _ _) = Just b
index n (Tree (One _) xs ys)
  | odd n = index ((n - 1) `div` 2) xs
  | otherwise = index ((n - 1) `div` 2) ys
index n (Tree (Two _ _) xs ys)
  | even n = index ((n - 2) `div` 2) xs
  | otherwise = index ((n - 2) `div` 2) ys