sec binary tree node implementations hidden from users of that tree class on the other handif the nodes are objects that have meaning to users of the tree separate from their existence as nodes in the treethen the version of figure might be preferred because hiding the internal behavior of the nodes becomes more important space requirements this section presents techniques for calculating the amount of overhead required by binary tree implementation recall that overhead is the amount of space necessary to maintain the data structure in other wordsit is any space not used to store data records the amount of overhead depends on several factors including which nodes store data values (all nodesor just the leaves)whether the leaves store child pointersand whether the tree is full binary tree in simple pointer-based implementation for the binary tree such as that of figure every node has two pointers to its children (even when the children are nullthis implementation requires total space amounting to ( dfor tree of nodes herep stands for the amount of space required by pointerand stands for the amount of space required by data value the total overhead space will be for the entire tree thusthe overhead fraction will be /( dthe actual value for this expression depends on the relative size of pointers versus data fields if we arbitrarily assume that dthen full tree has about two thirds of its total space taken up in overhead worse yettheorem tells us that about half of the pointers are "wastednull values that serve only to indicate tree structurebut which do not provide access to new data if only leaves store data valuesthen the fraction of total space devoted to overhead depends on whether the tree is full if the tree is not fullthen conceivably there might only be one leaf node at the end of series of internal nodes thusthe overhead can be an arbitrarily high percentage for non-full binary trees the overhead fraction drops as the tree becomes closer to fullbeing lowest when the tree is truly full in this caseabout one half of the nodes are internal great savings can be had by eliminating the pointers from leaf nodes in full binary trees because about half of the nodes are leaves and half internal nodesand because only internal nodes now have overheadthe overhead fraction in this case will be approximately ( + ( dn