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