# Heap-like notation of a BST (BFT bit-vectors) for succinct representation

I'm researching the topic of succinct tree representations right now and came across this presentation. On slide 17 there is an example of heap-like notation of a BST (using BFT bit-vectors) and the author claims that the amount of bits needed to represent a tree of $n$ elements (without their values) is exactly $2n+1$.

According to my calculations, it's $2n-1$. Here they are:

1. As in this representation every BST is represented as a complete tree, for the complete tree of height $k$ it has $2^{k+1}-1$ nodes.
2. On average for $n$ nodes tree has a height of $log_2n$.
3. Replacing the $k$ from the first list item with the average BST height from the second list item I received:

$$2^{log_2n+1}-1=2n-1$$

What am I missing in my calculations? Where do these 2 extra bits come from?

You can count it like this:

Let $n$ be the original number of nodes

Each original node has 2 children after adding the external nodes.

So 1 bit for the original node and 2 for its children. Total $3n$ bits.

But we are over counting here because original node is child of one other original node. So we subtract $n$ and get $2n$.

But we over corrected the count because root node has no parent so we add back 1 bit.

$2n + 1$.

• Thanks for your answer! This way it makes sense but using my calculations I still can't figure out why it lacks 2 additional bits (it should have some kind of explanation I hope). – ddnomad Oct 8 '16 at 17:26
• You are dealing with full binary trees and not complete binary trees. Now, full binary trees of height $k$ don't necessarily have $2^{k+1} -1$ nodes. Also, you don't really want to use average height of binary trees in your calculations since you are trying to derive a formula which tells how many bits the representation will require given a tree with $n$ nodes. Its not about the height of the tree. – Pratik Deoghare Oct 8 '16 at 18:21