Binary tree encoding Let's suppose you have a complete binary tree (i.e. each internal node has exactly two non empty descendants). Each node contains a nonzero integer. You are given the task of encoding and decoding the tree into/from a list of integers.

The tree is stored internally something like:

struct node {
  int data;
  struct node *left, *right;
};


And you have to implement two functions:

int *encode(struct node *root);
struct node *decode(int *array);


It is up to you how you encode and decode.

Points for:


minimum encoding length
complexity (ideally linear in number of nodes)
originality


No points for source code length and you are not restricted to C.

Tree example:

     5
    / \
   3   2
      / \
     2   1
    / \
   9   9
This Haskell program encodes a tree of n nodes in n Integers. The trick is that it encodes the node's data doubled, and then uses the lower-order bit to indicate if this is a leaf node, or an interior node.

Technically, the Parser monad here is over-kill, since there is only one parser created, decoder and I could have put the parser chaining logic directly there. But this way the decoder is very clear, and the Parser despite it's small size, is a reasonable simple parsing framework. 

import Control.Monad (ap)

data Tree = Leaf Integer | Node Integer Tree Tree
  deriving (Eq, Show)

encode :: Tree -&gt; [Integer]
encode (Leaf n)     = [n*2]
encode (Node n t u) = (n*2+1) : encode t ++ encode u

decode :: [Integer] -&gt; Maybe Tree
decode = fullyParse decoder
  where
    decoder :: Parser Integer Tree
    decoder = do
      i &lt;- next
      let n = i `div` 2
      if even i
        then return (Leaf n)
        else return (Node n) `ap` decoder `ap` decoder

-- A simple Parsing Monad
data Parser a b = P { runParser :: [a] -&gt; Maybe (b, [a]) }

instance Monad (Parser a) where
  return a = P ( \ts -&gt; Just (a, ts) )
  p &gt;&gt;= q  = P ( \ts -&gt; runParser p ts &gt;&gt;= (\(v,ts') -&gt; runParser (q v) ts') )
  fail _   = P ( const Nothing )

next :: Parser a a
next = P n
 where n (t:ts) = Just (t,ts)
       n _      = Nothing

fullyParse :: Parser a b -&gt; [a] -&gt; Maybe b
fullyParse p ts = runParser p ts &gt;&gt;= consumedResult
  where
    consumedResult (v,[]) = Just v
    consumedResult _      = Nothing

-- Example
main :: IO ()
main = do
    putStrLn $ "example:  " ++ show ex
    putStrLn $ "encoding: " ++ show encEx
    putStrLn $ "decoding: " ++ show decEx
    putStrLn $ "worked?   " ++ show worked
  where
    ex = Node 5
          (Leaf 3)
          (Node 2
            (Node 2
              (Leaf 9)
              (Leaf 9)
            )
            (Leaf 1)
          )
    encEx = encode ex
    decEx = decode encEx
    worked = maybe False (ex ==) decEx


Running this gets you:

&gt; runhaskell TreeEncoding.hs 
example:  Node 5 (Leaf 3) (Node 2 (Node 2 (Leaf 9) (Leaf 9)) (Leaf 1))
encoding: [11,6,5,5,18,18,2]
decoding: Just (Node 5 (Leaf 3) (Node 2 (Node 2 (Leaf 9) (Leaf 9)) (Leaf 1)))
worked?   True