Binary Tree array list representation

Question

I have been doing some research on Binary trees, and the array list representation. I am struggling to understand that the worst case space complexity is O(2^n). Specifically, the book states, the space usage is O(N) (N = array size), which is O(2^n) in the worst case . I would have thought it would have been 2n in the worst case as each node has two children (indexes) not O(2^n), where n = no. of elements.

an example, if I had a binary tree with 7 nodes, then the space would be 2n = 14 not 2^n = 128.

Answer 1

This is Heap implementation on an array. Where

A[1..n]
left_child(i) = A[2*i]
right_child(i) = A[2*i+1]
parent(i) = A[floor(i/2)]

Now, come to space. Think intuitively,

when you insert first element n=1, location=A[1], similarly,

n=2 @A[2] left_child(1)
n=3 @A[3] right_child(1)
n=4 @A[4] left_child(2)
n=5 @A[5] right_child(2)

You see, n^th element will go into A[n]. So space complexity is O(n).

When you code you just plug-in the element to be inserted in the end say at A[n+1], and say that it's a child of floor((n+1)/2).

Refer: http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

---

Heap is a nearly complete tree, so total number of elements in the tree would be 2h-1 < n <= 2h+1-1 and this is what the length of array you will need. Refer: this

Answer 2

The worst case space complexity of a binary tree is O(n) (not O(2^n) in your question), but using arrays to represent binary trees can save the space of pointers if it's nearly a complete binary tree.

See http://en.wikipedia.org/wiki/Binary_tree#Arrays

Answer 3

I think this refers to storing arbitrary binary trees in an array representation, which is normally used for complete or nearly complete binary trees, notably in the implementation of heaps.

In this representation, the root is stored at index 0 in the array, and for any node with index n, its left and right children are stored at indices 2n+1 and 2n+2, respectively.

If you have a degenerate tree where no nodes have any right children (the tree is effectively a linked list), then the first items will be stored at indices 0, 1, 3, 7, 15, 31, .... In general, the nth item of this list (starting from 0) will be stored at index 2n-1, so in this case the array representation requires θ(2n) space.