Storing a binary tree in an array

Question

Suppose there is a binary tree like the one below that should be stored in an array.

7 / \ 1 10 /\ 9 11 

And I found that the formula for storing nodes in an array starts by saving the root of the node at position 0, and then for each node with index i its children are placed at indexes (i*2)+1 and (i*2)+2 , And if the index of any of them is greater than array.length - 1 , then node has no children.

So, I start by placing 7 at position 0, then his children 1 and 10 at positions i2 + 1 and i2 + 2, which will be 1 and 2:

 |7|1|10| | | | 0 1 2 3 4 5 

Now I am stuck with node 1 that has no children. What should I put as my children?

Is it possible to put a default value that will mean the absence of a node, for example, -1, for example:

 |7|1|10|-1|-1|9|11| 0 1 2 3 4 5 6 7 

Answer 1

This algorithm for storing a binary tree in an array is designed for trees, so that each branch of the tree starting with the root of the node has the same length: the size of the array is based on the greatest depth in the tree, and then assigns the position of the array for each tree position to equal or less depth. If you have many different branch lengths, this may not be the right algorithm for you. If the lengths of the branches basically have the same depth, but sometimes empty at the end of the tree, placing a null value such as -1 or Integer.MIN_VALUE may be the appropriate solution if you know that you will usually not need to put any -1 values ​​in the tree .

If you know that you will not have elements from the highest depth level of your tree (as in the example you specified), and the left / right order of the tree does not matter, instead you can simply reorder your tree, so empty values always in the bottom, right position, which is also the set of positions at the end of your array, thereby making your tree a complete binary tree . Then you need to remember only the number of elements in the tree, which is greater than the index of the last nonzero value. Schematically:

  7 / \ 10 1 /\ 9 11 --> |7|10|1|9|11|0|0| 0 1 2 3 4 5 6 length = 5 or lastIndex = 4 

Answer 2

I was thinking about using values ​​that at this moment violate the binary tree property. In a shared binary tree, Left is always smaller and to the right larger than the current node. If the meeting is higher left or lower right means the end nodes.