discussion on techniques for determining the space requirements for given binary tree node implementation the section concludes with an introduction to the arraybased implementation for complete binary trees pointer-based node implementations by definitionall binary tree nodes have two childrenthough one or both children can be empty binary tree nodes normally contain value fieldwith the type of the field depending on the application the most common node implementation includes value field and pointers to the two children figure shows simple implementation for the binnode abstract classwhich we will name bstnode class bstnode includes data member of type (which is the second generic parameterfor the element type to support search structures such as the binary search treean additional field is includedwith corresponding access methodsstore key value (whose purpose is explained in section its type is determined by the first generic parameternamed key every bstnode object also has two pointersone to its left child and another to its right child figure shows an illustration of the bstnode implementation some programmers find it convenient to add pointer to the node' parentallowing easy upward movement in the tree using parent pointer is somewhat analogous to adding link to the previous node in doubly linked list in practicethe parent pointer is almost always unnecessary and adds to the space overhead for the tree implementation it is not just problem that parent pointers take space more importantlymany uses of the parent pointer are driven by improper understanding of recursion and so indicate poor programming if you are inclined toward using parent pointerconsider if there is more efficient implementation possible an important decision in the design of pointer-based node implementation is whether the same class definition will be used for leaves and internal nodes using the same class for both will simplify the implementationbut might be an inefficient use of space some applications require data values only for the leaves other applications require one type of value for the leaves and another for the internal nodes examples include the binary trie of section the pr quadtree of section the huffman coding tree of section and the expression tree illustrated by figure by definitiononly internal nodes have non-empty children if we use the same node implementation for both internal and leaf nodesthen both must store the child pointers but it seems wasteful to store child pointers in the leaf nodes thusthere are many reasons why it can save space to have separate implementations for internal and leaf nodes