Storing binary trees

Computer Science Level 3

Binary trees can be stored in an array as follows:

Indexing of the array starts at $1$ instead of $0$ . For an array $P$ , the root is stored at $P[1]$ . For a node stored at $P[i]$ , the left child, if any, is stored in $P[2i]$ and the right child, if any, in $P[2i+1]$ .

What should be the minimum size of array $P$ to be able to store any binary tree of $n$ vertices?

\log _{ 2 }{ 2n }

2^{n}-1

2n+1

n

1 solution

Andrea Temin
Mar 16, 2016

I think that the answer should be 2^h - 1 where h is the height of the tree, in this way you have almost a perfect optimization of the array's length for differents trees with the same number of nodes but with a different permutations.

Storing binary trees

1 solution

0 pending reports