CODEWITHSUNDEEP
javaalgorithmbinary-search-tree
VCODE
VCODE

Reputation: 700

Storing a binary tree in an array

Suppose that there's a binary tree like the one below that needs to be stored in an array.

    7
   / \
  1  10
     /\
    9  11

And I found that the formula for storing the nodes in the array begins with storing the root node at position 0, and then for every node at index i, its children are placed at indices (i*2)+1 and (i*2)+2. And if the index of either child is greater than the array.length - 1, then that node does not have children.

So I begin by putting 7 at position 0, then its children 1 and 10 at position i2+1 and i2+2 which would be 1 and 2:

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

Now, I'm stuck with node 1 which does not have any children. What should I put as its children?

Is it OK to put some default value that would represent the absence of a node, for example -1, like this:

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

Upvotes: 6

Views: 5899

Answers (2)

ModProbe
ModProbe

Reputation: 1

I was thinking of using values which will break binary tree property at this point. In a general binary tree Left is always smaller and right is bigger than current node. If encounter higher on left or lower on right means end nodes.

Upvotes: 0

Vitruvie
Vitruvie

Reputation: 2327

This algorithm for storing a binary tree in an array is designed for trees such that every branch of the tree starting from the root node is of the same length: the array size is based on the greatest depth within the tree, and then it assigns an array position for every tree position of equal or lesser depth. If you have many different branch lengths, this may not be the correct algorithm for you. If your branch lengths are mostly the same depth but are sometimes empty near the end of the tree, placing a 'null' value such as -1 or Integer.MIN_VALUE may be an appropriate solution, as long as you know that you will not normally need to place any -1 values into the tree.

If you happen to know that you will only be missing elements from the greatest depth level of your tree (as in the example you provided), and the left/right order of the tree does not matter, you can instead simply reorder your tree such that the empty values are always in the bottommost, rightmost positions, which is also the set of positions at the end of your array, thus making your tree a complete binary tree. Then, you need only remember the number of elements in the tree, which is one greater than the index of the last non-null value. Diagrammed:

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

Upvotes: 3

Related Questions