1

I happened to come across a flattened array representation for a Binary Tree data structure, where all the values on the tree are stored in an array that corresponds to an index tree.

I was wondering how to store null value at the array indices where there is no leaf node. I am assuming that the reference was in Java. In C++, how do we obtain a null value that does not equal 0. Should we use an array of pointers instead? One which allows the pointers to point to node values (if they exist) or assume a nullptr (when node value is null).

I do not plan to use NULL value from C++ as it equates to 0 integer, which will cause conflict in case of an integer array.

Please let me know if you need clarification.

Example Image

Improve this question
5
  • You can circumvent the problem by requiring that the last layer is filled left-to-right, in which case you simply need to know how long the filled prefix of the array is (=size of the tree). Commented Dec 27, 2020 at 11:33
  • 2
    You can store pointers to dynamically allocated objects. If you want to avoid dynamic allocation, you can store std::optional<T>, which holds T inside itself. Commented Dec 27, 2020 at 11:42
  • The property Norrius refers to means it is generally referred to as a "binary heap", and the process of ensuring the nodes are stored to guarantee this constraint is sometimes referred to as 'heapifying' the array. See: en.wikipedia.org/wiki/Binary_heap Commented Dec 27, 2020 at 11:42
  • Review: Why was this Q downvoted? I think it isn't that bad. Though a code sample of what was tried could be helpful. Commented Dec 27, 2020 at 12:02
  • If your array contains elements of int there is no other way as assuming a certain int value as invalid (and handle it respectively). If 0 is not a reasonable candidate, you could use -1 or anything else which you don't consider as valid value for a node. If all int values are potentially valid than you have to store something else paired with your values e.g. a bool. This is similar to std::optional<T> which was already suggested by @Evg. Commented Dec 27, 2020 at 12:26

1 Answer 1

Reset to default
1

Use -1.

No, seriously.

There is even at least one platforms where C or C++ nullptr is -1. It does require careful cast-to-bool (well, cast-to/from-integral; 0 must convert to nullptr under the standard but the bit pattern of a null ptr doesn't have to be all 0s) code.

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

2 Comments

There are even platforms where C++ nullptr is -1. Could you please name one?
@evg no I cannot; but, if I decall, it is a gpu where 0 is a valid address, while -1 is not. Might have been C rather than C++.

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.