Binary Trees, arrays vs linked

binary tree

In general, binary tree based abstractions can be implemented either using actual linked node objects, where each node has pointers to it's two children, or an array, where the children of node in index k are 2k and 2k+1.

Other than the small extra memory overhead of nodes, the complexity in general seems to be identical.

Are there any concrete advantages of one over the other? Anecdotally, I've seen that binary heaps tend to use the array implementation, while binary search trees tend to use linked nodes implementation. Any reason for this?

Best Answer

Arrays cannot efficiently represent arbitrarily-shaped binary trees, only complete trees. A complete binary tree is one in which all levels are full, OR all levels except the deepest level are full and the deepest level has all of its nodes as far to the left as possible. (You can imagine that the levels are filled with nodes from left to right, and one level has to be filled before the next level can begin.)

Heaps are, by definition, complete binary trees - hence the array implementation is used due to its superior memory efficiency. On the other hand, binary search trees that must support insertion and removal at arbitrary locations (and thus may not be complete trees) cannot use the array implementation.

Related Topic