Efficient Array Storage for Binary Tree

Question

We have to write the nodes of a binary tree to a file. What is the most space efficient way of writing a binary tree . We can store it in array format with parent in position i and its children in 2i, 2i+1. But this will waste lot of space in case of sparse binary trees.

Solution 1

The 2i, 2i+1 (Binary Heap) method is indeed the best way if you have a (nearly) complete tree.

Otherwise you won't escape storing a ParentId (parent Index) with each node.

Solution 2

Think about XML. It's a kind of tree serialization. For example:

<node id="1">
    <node id="2">                                   1
    </node>                                       /   \
    <node id="3">                                2     3
        <node id="4">                                 / \
        </node>                                      4   5
        <node id="5">
        </node>
    </node>
</node>

Then, why the spaces and tags ? We can omit them, step by step:

<1>
   <2></>
   <3>
     <4></>
     <5></>
   </>
</>

Remove the spaces: <1><2></2><3><4></><5></></></>.

Remove the angle brackets: 12/34/5///

Now the problem is: what if a node has a empty left subtree and non-empty right subtree? Then we can use another special charactor, '#' to represent an empty left sub-tree.

For example:

    1
  /   \
      2
     /  \
    3

This tree can be serialized as: 1#23///.

Solution 3

You can save the in-order and pre/post-order traversal of the binary tree in the file and reconstruct the tree from these traversals.

Comments

[Sundararajan S]

this case i will always consume 2n space (n for inorder and n for post order).

[JavaDeveloper]

This is also using 2n space, how is this any better than preoder/inorder ?

[Ben Jones]

Nice suggestion. One nit: I believe level-order is the output of BFS (breadth first) not DFS (depth first)