chap binary trees if dthe overhead drops to about one half of the total space howeverif only leaf nodes store useful informationthe overhead fraction for this implementation is actually three quarters of the total spacebecause half of the "dataspace is unused if full binary tree needs to store data only at the leaf nodesa better implementation would have the internal nodes store two pointers and no data field while the leaf nodes store only data field this implementation requires ( units of space if dthen the overhead is about /( + / it might seem counter-intuitive that the overhead ratio has gone up while the total amount of space has gone down the reason is because we have changed our definition of "datato refer only to what is stored in the leaf nodesso while the overhead fraction is higherit is from total storage requirement that is lower there is one serious flaw with this analysis when using separate implementations for internal and leaf nodesthere must be way to distinguish between the node types when separate node types are implemented via java subclassesthe runtime environment stores information with each object allowing it to determinefor examplethe correct subclass to use when the isleaf virtual function is called thuseach node requires additional space only one bit is truly necessary to distinguish the two possibilities in rare applications where space is critical resourceimplementors can often find spare bit within the node' value field in which to store the node type indicator an alternative is to use spare bit within node pointer to indicate node type for examplethis is often possible when the compiler requires that structures and objects start on word boundariesleaving the last bit of pointer value always zero thusthis bit can be used to store the nodetype flag and is reset to zero before the pointer is dereferenced another alternative when the leaf value field is smaller than pointer is to replace the pointer to leaf with that leaf' value when space is limitedsuch techniques can make the difference between success and failure in any other situationsuch "bit packingtricks should be avoided because they are difficult to debug and understand at bestand are often machine dependent at worst array implementation for complete binary trees the previous section points out that large fraction of the space in typical binary tree node implementation is devoted to structural overheadnot to storing data in the early to mid si worked on geographic information system that stored spatial data in quadtrees (see section at the time space was critical resourceso we used bit-packing approach where we stored the nodetype flag as the last bit in the parent node' pointer this worked perfectly on various -bit workstations unfortunatelyin those days ibm pc-compatibles used -bit pointers we never did figure out how to port our code to the -bit machine