# Succinct Encoding of Binary Tree

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.

Below is algorithm for encoding:

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
}

Example:

Input:
10
/
20       30
/
40   50      70

Data Array (Contains preorder traversal)
10 20 40 50 30 70

Structure Array
1 1 1 0 0 1 0 0 1 0 1 0 0
1 indicates data and 0 indicates NULL

Below is C++ implementation of above algorithms.

## C++

 // C++ program to demonstrate Succinct Tree Encoding and decoding #include using namespace std;    // A Binary Tree Node struct Node {     int key;     struct Node* left, *right; };    // Utility function to create new Node Node *newNode(int key) {     Node *temp = new Node;     temp->key  = key;     temp->left  = temp->right = NULL;     return (temp); }    // This function fills lists 'struc' and 'data'.  'struc' list // stores structure information. 'data' list stores tree data void EncodeSuccinct(Node *root, list &struc, list &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 &struc, list &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; }    // A utility function to print tree void preorder(Node* root) {     if (root)     {         cout << "key: "<< root->key;         if (root->left)             cout << " | left child: " << root->left->key;         if (root->right)             cout << " | right child: " << root->right->key;         cout << endl;         preorder(root->left);         preorder(root->right);     } }    // Driver program int main() {     // Let us construct the Tree shown in the above figure     Node *root         = newNode(10);     root->left         = newNode(20);     root->right        = newNode(30);     root->left->left   = newNode(40);     root->left->right  = newNode(50);     root->right->right = newNode(70);        cout << "Given Tree ";     preorder(root);     list struc;     list  data;     EncodeSuccinct(root, struc, data);        cout << " Encoded Tree ";     cout << "Structure List ";     list::iterator si; // Structure iterator     for (si = struc.begin(); si != struc.end(); ++si)         cout << *si << " ";        cout << " Data List ";     list::iterator di; // Data iIterator     for (di = data.begin(); di != data.end(); ++di)         cout << *di << " ";        Node *newroot = DecodeSuccinct(struc, data);        cout << " Preorder traversal of decoded tree ";     preorder(newroot);        return 0; }

## Python

 # Python program to demonstrate Succient Tree Encoding and Decoding    # Node structure class Node:     # Utility function to create new Node      def __init__(self , key):         self.key = key          self.left = None         self.right = None    def EncodeSuccint(root , struc , data):            # If root is None , put 0 in structure array and return     if root is None :         struc.append(0)         return        # Else place 1 in structure array, key in 'data' array     # and recur for left and right children     struc.append(1)     data.append(root.key)     EncodeSuccint(root.left , struc , data)     EncodeSuccint(root.right , struc ,data)           # Constructs tree from 'struc' and 'data' def DecodeSuccinct(struc , data):     if(len(struc) <= 0):         return None            # Remove one item from structure list     b = struc[0]     struc.pop(0)            # If removed bit is 1     if b == 1:          key = data[0]         data.pop(0)                #Create a tree node with removed data         root = Node(key)            #And recur to create left and right subtrees         root.left = DecodeSuccinct(struc , data);         root.right = DecodeSuccinct(struc , data);         return root        return None       def preorder(root):     if root is not None:         print "key: %d" %(root.key),                        if root.left is not None:             print "| left child: %d" %(root.left.key),         if root.right is not None:             print "| right child %d" %(root.right.key),         print ""         preorder(root.left)         preorder(root.right)    # Driver Program root = Node(10) root.left = Node(20)  root.right = Node(30) root.left.left = Node(40) root.left.right = Node(50) root.right.right = Node(70)             print "Given Tree" preorder(root) struc = [] data = [] EncodeSuccint(root , struc , data)    print " Encoded Tree" print "Structure List"    for i in struc:     print i ,    print " DataList" for value in data:     print value,    newroot = DecodeSuccinct(struc , data)    print " Preorder Traversal of decoded tree" preorder(newroot)    # This code is contributed by Nikhil Kumar Singh(nickzuck_007)

Output:

Given Tree
key: 10 | left child: 20 | right child: 30
key: 20 | left child: 40 | right child: 50
key: 40
key: 50
key: 30 | right child: 70
key: 70

Encoded Tree
Structure List
1 1 1 0 0 1 0 0 1 0 1 0 0
Data List
10 20 40 50 30 70

Preorder traversal of decoded tree
key: 10 | left child: 20 | right child: 30
key: 20 | left child: 40 | right child: 50
key: 40
key: 50
key: 30 | right child: 70
key: 70

## tags:

Tree catalan Tree