Array vs Linked List Representation of Binary Tree
- Arrays cannot 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.