I am trying to implement different types of array-based BST implementations. Namely, let's assume we have a tree like this:
3
/ \
1 5
/ \ / \
0 2 4 6
Now, the above can be represented as a sorted array (Repr 1): [0,1,2,3,4,5,6], as if we built the above tree using recursion and finding middle element in every step.
It can also be represented as a level-based tree, aimilar to what heap uses (Repr 2): [3,1,5,0,2,4,6], with children of i at 2i+1 and 2i+2.
I have some questions regarding building the above representations:
- To convert a tree to Repr 1, we can use some form of in-order traversal algorithm. To build Repr 2, we can use BFS-based traversal. The reverse algorithms (from array to tree) are well-known. My questions is, how do I convert Repr 1 to Repr 2? I tried to approach it iteratively, but my main problem is finding out indices of children. I.e. root is at
n/2but then how do I come up with formula for left/right child and process the rest of the array? - With Repr 1, is it possible to allow insertions? In simple recursive traversal we can find index of parent, but again, where should we insert the child (providing the array has free space to do so)
question 1: python implementation (i'm sorry i don't believe a specific language was chosen so i picked the one i'm most comfortable with)
question 2: i have no clue honestly