Editing Binary tree (section)

=== Succinct encodings ===
A [[succinct data structure]] is one which occupies close to minimum possible space, as established by [[information theory|information theoretical]] lower bounds. The number of different binary trees on <math>n</math> nodes is <math>\mathrm{C}_{n}</math>, the <math>n</math>th [[Catalan number]] (assuming we view trees with identical ''structure'' as identical). For large <math>n</math>, this is about <math>4^{n}</math>; thus we need at least about <math>\log_{2}4^{n} = 2n</math> bits to encode it. A succinct binary tree therefore would occupy {{nowrap|2''n''+o(''n'')}} bits (with 'o()' being the [[Little-o notation]]).

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.<ref>{{cite web |last1=Demaine |first1=Erik |title=6.897: Advanced Data Structures Spring 2003 Lecture 12 |url=http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L12/lecture12.pdf |publisher=MIT CSAIL |access-date=14 April 2022 |archive-url=https://web.archive.org/web/20051124175104/http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L12/lecture12.pdf |archive-date=24 November 2005 |url-status=dead}}</ref> If the tree contains data, we can simply simultaneously store it in a consecutive array in preorder. This function accomplishes this:

 '''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);
 }

The string ''structure'' has only <math>2n + 1</math> bits in the end, where <math>n</math> is the number of (internal) nodes; we don't even have to store its length. To show that no information is lost, we can convert the output back to the original tree like this:

 '''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
 }

More sophisticated succinct representations allow not only compact storage of trees but even useful operations on those trees directly while they're still in their succinct form.