Storing a binary tree in an array

Question

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

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

I am not sure why you would have to worry about the children. If you plan on putting it back into a tree at some time your tree builder will take care of balancing, you should only have the numbers that are in the tree in the array not any placeholders. — David Coler
– David Coler, Commented Dec 24, 2014 at 20:14
good question. if I were you, I would put -999999 just to show null — Kick Buttowski
– Kick Buttowski, Commented Dec 24, 2014 at 20:14
@KickButtowski -999999 is a poor choice of null constant; it only encourages strange bugs when things just happen to add up to -999999. Better constants would be -1 (if you only start at zero and add) or Integer.MIN_VALUE (if you expect numbers to be near zero and would have trouble with int overflow anyway) — Vitruvie
– Vitruvie, Commented Dec 24, 2014 at 20:18
You ask if there's a better way, but it is difficult to know. Chances are you can use a standard data library. What language are you working in? Please identify properties of the tree, if it has any expected properties you can identify, such as fullness, completeness, depth, etc. (gamedev.net/tags/ccs/binary) Can you tell us what is generating the tree? — dwn
– dwn, Commented Dec 24, 2014 at 20:23

Kick Buttowski · Accepted Answer · 2014-12-24 22:43:35Z

3

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

edited Dec 24, 2014 at 22:43

Kick Buttowski

6,74713 gold badges39 silver badges61 bronze badges

answered Dec 24, 2014 at 20:16

Vitruvie

2,33519 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

VCODE Over a year ago

I think this makes sense. Actually I was learning about heaps and I saw some examples where the nodes from the far right don't have children, eg: en.wikipedia.org/wiki/Heap_%28data_structure%29#mediaviewer/…, and I though that this is just a coincidence and was curios what if it is the other way around, the nodes from the left side don't have children. So, can I assume that a valid heap tree should not be empty at the start of the tree?

Vitruvie Over a year ago

@VCODE Added another solution for the case when your tree is complete, as when it represents a heap.

ModProbe · Accepted Answer · 2014-12-25 10:52:44Z

0

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.

answered Dec 25, 2014 at 10:52

ModProbe

11 bronze badge

Collectives™ on Stack Overflow

Storing a binary tree in an array

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related