1

In university we were asked how we would save an incomplete binary tree into an array. The indices would be 2i+1 for the left child and 2i+2 for the right child of a Vertex. floor((i − 1)/2) for the parent node. The first question now was how we would represent the "missing" vertexes.

I think that could be accomplished just by saving "null" into the Array. Are there any better solutions?

The second question is the point where I clearly don't have any idea what to answer. It was asked why no one would actually do that and which severe problems can occur if we implement the problem from the first question like that.

Thanks for your help.

Improve this question
1
  • When you say you would use "null", what do you mean? For all the nodes missing from a complete tree, or just the root node of a missing subtree? The former is simpler but may take exponentially more memory than necessary to represent an incomplete tree; the latter is more complex but takes space proportional to the number of nodes actually in the tree. Commented Jul 25, 2017 at 18:27

1 Answer 1

Reset to default
1

The answer to how to represent the missing vertices depends on your language. In Java, if your array is one of Objects than you can certainly use null. If it is an array of primitives than you need some sort of sentinel value that can represent null. As mentioned, using an array to represent a non-complete binary tree can be wasteful depending on the structure of your tree.

The answer to the second question is probably the above issue with memory. With that said, there are other ways to store a non-complete tree in an array that are less abusive to memory but they are more complicated than simply "left child at 2i+1 and right child at 2i+2".

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

1 Comment

Can you elaborate on the more complicated versions? I've seen this question which shows an interesting way of basically shifting child nodes forward to fill holes left by missing nodes. It saves space but seems like it requires unpacking in order to traverse.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.