What is the best way to implement Tree : LinkedList - Array

Question

I am preparing for an exam, one of the questions I came across is : what is the best way to implement tree, LinkedList or Array.

Most likely: - Array uses 1 address - LinkedList use two addresses.

Using LinkedList, we can insert the value we need (we manage perfectly the memory), but most likey use O(N) to access to this element, while in Array it O(1).

How should I answer this question ? Or should I just say that is subjective.

Answer 1

For a Binary Search Tree, the answer would definitely be an array ( at least hopefully an extendable array, like a vector<> so you aren't limited to a fixed size). I'll do an analysis of the common operations, assuming the tree is balanced.

Query

In a BST, nodes need to have pointers to left and right children and is also very common to have parent pointers. In an array implementation, the "pointers" can simply be integer indexes into the array ( this would mean the array would store Node objects). Thus looking up the parent and children of a node is constant since indexing into the array is constant. O(1). A linked list implementation would probably need to also store a reference to the position as to where their ancestors/children are, thus requiring an O(N) pass through the list to get the desired references.

Search

Starting at the root, array[0], searching would be an O(log N) operation. Searching would just call/get the info of the children per node, which is O(1) amount of work, roughly O(log N) times, thus O(log N) for search in an array.

A linked list would require an O(N) pass through the data to get the required left/right pointers, and can also be done in O(log N) steps, thus producing an O(n log n) search in linked-lists.

Insert

Arrays would be similar to search, except would require additional O(1) constant time for pointer assignments. So O(log N) insert.

Linked-lists would also be similar to their search routine, except with an additional O(n) time for adjusting the pointers, so O(n log n)

Delete

Arrays would also be similar to search, except you could take more than a single O(log n) factor to delete, since you have to traverse back up the tree, but it still is O(log n).

Linked lists would too have the O(n log n) plus more O(n log n) for traversing up. So O(n log n) for linked lists as well.

Conclusion

The answer should be fairly evident by now :) Plus with arrays you'll get the benefit of better caching than linked-lists. Plus, some derivatives of binary search trees, such as heaps (usually min-heaps/max-heaps) are commonly represented as arrays,

I hope this helps :)