Succinct Encoding of Binary Tree - GeeksforGeeks

Succinct Encoding of Binary Tree - GeeksforGeeks
A succinct encoding of Binary Tree takes close to minimum possible space. The number of structurally different binary trees on n nodes is n’th Catalan number. For large n, this is about 4n; thus we need at least about log2 4 n = 2n bits to encode it. A succinct binary tree therefore would occupy 2n+o(n) bits.

One simple representation which meets this bound is to visit the nodes of the tree in preorder, 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 preorder.
https://en.wikipedia.org/wiki/Binary_tree#Succinct_encodings

function EncodeSuccinct(node n, bitstring structure, array data) {
    if n = nil then
        append 0 to structure;
    else
        append 1 to structure;
        append n.data to data;
        EncodeSuccinct(n.left, structure, data);
        EncodeSuccinct(n.right, structure, data);
}

And below is algorithm for decoding

function DecodeSuccinct(bitstring structure, array data) {
    remove first bit of structure and put it in b
    if b = 1 then
        create a new node n
        remove first element of data and put it in n.data
        n.left = DecodeSuccinct(structure, data)
        n.right = DecodeSuccinct(structure, data)
        return n
    else
        return nil
}

// This function fills lists 'struc' and 'data'.  'struc' list

// stores structure information. 'data' list stores tree data

void EncodeSuccinct(Node *root, list<bool> &struc, list<int> &data)

{

    // If root is NULL, put 0 in structure array and return

    if (root == NULL)

    {

        struc.push_back(0);

        return;

    }

 

    // Else place 1 in structure array, key in 'data' array

    // and recur for left and right children

    struc.push_back(1);

    data.push_back(root->key);

    EncodeSuccinct(root->left, struc, data);

    EncodeSuccinct(root->right, struc, data);

}

 

// Constructs tree from 'struc' and 'data'

Node *DecodeSuccinct(list<bool> &struc, list<int> &data)

{

    if (struc.size() <= 0)

        return NULL;

 

    // Remove one item from from structure list

    bool b = struc.front();

    struc.pop_front();

 

    // If removed bit is 1,

    if (b == 1)

    {

         // remove an item from data list

        int key = data.front();

        data.pop_front();

 

        // Create a tree node with the removed data

        Node *root = newNode(key);

 

        // And recur to create left and right subtrees

        root->left = DecodeSuccinct(struc, data);

        root->right = DecodeSuccinct(struc, data);

        return root;

    }

 

    return NULL;

}

 

Read full article from Succinct Encoding of Binary Tree - GeeksforGeeks