Homework 7-4
=
###### tags: `Course - Algorithmics`
## Design
We can use Succinct's encoding algorithm.
Visit the nodes of the tree in <font color=#0000FF>**preorder**</font>, outputting “1” for an internal node and “0” for a leaf. If the tree contains data, we can simply simultaneously store it in a consecutive array in <font color=#0000FF>**preorder**</font>.
## Pseudo Code
* Encode

result = bitstring() # Encoded tree
data = list() # Data of nodes
EncodeSuccinct(myTree.root, result, data) # myTree is the given tree

def EncodeSuccinct(n, result, data):
    if n == NULL:
        result.append(0);
    else:
        result.append(1);
        data.append(n.data);
        EncodeSuccinct(n.left, result, data);
        EncodeSuccinct(n.right, result, data);

* Decode

myTreeRestored.root = DecodeSuccinct(result, data)

def DecodeSuccinct(source, data):
    b = source.pop(0) # remove first bit of source and put it into b
    if b == 1: # it was an internal node
        n = node() # create a new node n
        n.data = data.pop(0)
        n.left = DecodeSuccinct(source, data)
        n.right = DecodeSuccinct(source, data)
        return n
    else: # it was a leaf node
        return NULL

## Analysis
* Time complexity
$\Theta(n)$
* Space complexity
$\Theta(lg{(n)})$
* Encoded size
$2n+\Theta(n)$
2n is the size of the code, and $\Theta(n)$ is the size of node data.