Editing Binary tree (section)

== Encodings ==

=== 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 <math>2n+o(n)</math> 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.<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.

=== Encoding ordered trees as binary trees ===
There is a natural one-to-one correspondence between ordered trees and binary trees. It allows any ordered tree to be uniquely represented as a binary tree, and vice versa:

Let ''T'' be a node of an ordered tree, and let ''B'' denote ''T's'' image in the corresponding binary tree. Then ''B's'' ''left'' child represents ''T's'' first child, while the ''B's right'' child represents ''T'''s next sibling. 

For example, the ordered tree on the left and the binary tree on the right correspond:

[[Image:N-ary to binary.svg|400x240px|center|An example of converting an n-ary tree to a binary tree]]

In the pictured binary tree, the black, left, edges represent ''first child'', while the blue, right, edges represent ''next sibling''.

This representation is called a [[left-child right-sibling binary tree]].