434,917 Members | 1,305 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 434,917 IT Pros & Developers. It's quick & easy.

Analytical solution to predict array size of binary tree

 P: 1 I'm constructing a binary tree for a sequence of data and the tree is store in a 1-based array. So if index of parent node is idx, the left child is 2 * idx and the right is 2 * idx + 1. Every iteration, I sort current sequence based on certain criteria, select the median element as parent, tree[index] = sequence[median], then do same operation on left(the sub sequence before median) and right(the subsequence after median) recursively. Eg, if 3 elements in total, the tree will be: 1 / \ 2 3, the array size to store the tree is also 3 4 elements: 1 / \ 2 3 / 4 , the array size to store the tree is also 4 5 elements: 1 / \ 2 3 / \ / 4 null 5 , the array size to store the tree has to be 6, since there is a hole between 4 and 5. Thus, the array size is only determined by number of elements, I believe there is an anlytical solution for it, just can't prove it. Any suggestion will be appreciated. Thanks. Jan 16 '19 #1 