I am creating a binary radix tree(longest common prefix tree). The data is stored only in leaf nodes. The tree hierarchy has internal nodes and each internal node has two child nodes. A child node can either be a leaf node or internal node. Both leaf nodes and internal nodes store a reference to parent node.
Leaf nodes are stored in an array. internal nodes are stored in another array. Root node is first element of internal node array
Node
{
Node* parent;
}
LNode: Node
{
data;
}
INode: Node
{
Node* leftchild;
Node* rightchild;
}
Assuming that the tree structure is filled now as an array of internal nodes, if I now pick any internal node of the tree, how do I know whether the child node of the internal node is an internal node or leaf node ? to do this I am thinking of storing one Boolean variable for each child node to mark it as either a lead node or internal node. But this doesn't seem to me to be a good solution.
Can anyone suggest me a better way to do this ?