Are structs necessary in binary search trees

Question

I've looked at some code for BSTs and I can see that each node is a struct. Is this necessary?

Answer 1

int flat_tree[ 1000 ][ 3 ];
    // for each tree node, value is stored in element [id][0]
                        // id of left_child stored in element [id][1]
                        // id of right_child stored in element [id][2]

…

I'm not gonna go any further with this.

Generally speaking, structs/classes are used for any kind of linked data structure. Also generally, any feature of the type system may be defeated or ignored and you can do everything (heap allocation, etc) in one array of ints in very painful fashion.

Answer 2

No, it could be a class. It can't be a primitive, because it needs to store a value and also point to children.

Well, I should say that you could also represent your BST as an array, where the left and right children of the node at position i are in positions 2 * i + 1 and 2 * i + 2, respectively. But then you would have to worry about resizing, and you would need a special value to represent null, and delete operations become pretty complicated. I don't recommend this approach as anything other than an academic exercise.

Answer 3

Its not mandatory.
But since the data a node contains along with the two links together form a logical entity they are usually put together in a struct. So that it becomes easier to code functions that take a node as an argument or return a node.

Answer 4

No, not strictly speaking. In the FORTRAN days, people used parallel arrays, or two-dimensional arrays.

Tony Hoare's section of "Structured Programming" by Dahl, Dijkstra, and Hoare, talked about data structuring and record types.

Answer 5

You can do simpler than parallel arrays if your payload admits a sentinal value: you can use a implicit tree (that is, not bother with links at all).

payload_type a[tree_size];

Just a long flat array containing only payload values, with position in the array coding for link structure:

• a[0] is root
• a[1] is root->left
• a[2] is root->right
• a[3] is root->left->left
• a[4] is root->left->right
• ...

For the node at position i, go to 2*i+1 for left and 2*i+2 for right

You initialize it to all sentinal values, and start adding things...