CODEWITHSUNDEEP
arraysheightbinary-treebinary-search-tree
jM2.me
jM2.me

Reputation: 3969

How to calculate array size for a binary search tree with a certain height?

I am working on binary search tree implementation using array. I need to create an array for a BST with a specific height. How do I calculate that size?

Upvotes: 1

Views: 6601

Answers (1)

user2104560
user2104560

Reputation:

I guess, you are talking about implementation with indexation like in a binary heap.

All vertices stored in array. First element of this array - root. If some vertex of BST is i-th element of array, it's left son stored in cell with index 2*i, right son - in cell with index 2*i+1. The scheme of such representation in memory is shown below:

You are asking about tree size for some given height. Height - is a number of levels in a tree. In other words, height is a length of the path from root to any leaf. In the picture above BST has height = 2.

How calulate size of array for storing tree with fixed height? It's just sum of geometrical progression. Level with height = 0 has 1 element, next level with height=1 has 2 elements, next level has 4 elements and so on. Level with height = H has 2^H elements.

Array size for storing tree with height = H is size enough for storing all levels from 0 to H:
2^0 // cells for level with height=0
+
2^1 // cells for level with height=1
+...
+2^H = 2^(H+1)-1;

Important note - many programming languages has zero-based array indexation. So, when you declare array like int tree[2^(H+1)-1] it means that elements numbered from 0 to 2^(H+1)-2 while you want them be numbered from 1 to 2^(H+1)-1. Element with index 0 is not convenient - it breaks "parent i,left son 2*i" rule because 0=2*0. In other words when I say first element in array is a root I mean tree[1], not tree[0]. Just ignore tree[0].

Finally, required_array_size for BST with height H = calculated_size + zero_ignoring_shift = 2^(H+1)-1 +1 = 2^(H+1)

Upvotes: 4

Related Questions