chap advanced tree structures mation for node save considerable spacebut avoiding storing such information in the nodes we enables good design choice for empty leaf nodesas discussed next how should we represent empty leaf nodeson averagehalf of the leaf nodes in pr quadtree are empty ( do not store data pointone implementation option is to use null pointer in internal nodes to represent empty nodes this will solve the problem of excessive space requirements there is an unfortunate side effect that using null pointer requires the pr quadtree processing methods to understand this convention in other wordsyou are breaking encapsulation on the node representation because the tree now must know things about how the nodes are implemented this is not too horrible for this particular applicationbecause the node class can be considered private to the tree classin which case the node implementation is completely invisible to the outside world howeverit is undesirable if there is another reasonable alternative fortunatelythere is good alternative it is called the flyweight design pattern in the pr quadtreea flyweight is single empty leaf node that is reused in all places where an empty leaf node is needed you simply have all of the internal nodes with empty leaf children point to the same node object this node object is created once at the beginning of the programand is never removed the node class recognizes from the pointer value that the flyweight is being accessedand acts accordingly note that when using the flyweight design patternyou cannot store coordinates for the node in the node this is an example of the concept of intrinsic versus extrinsic state intrinsic state for an object is state information stored in the object if you stored the coordinates for node in the node objectthose coordinates would be intrinsic state extrinsic state is state information about an object stored elsewhere in the environmentsuch as in global variables or passed to the method if your recursive calls that process the tree pass in the coordinates for the current nodethen the coordinates will be extrinsic state flyweight can have in its intrinsic state only information that is accurate for all instances of the flyweight clearly coordinates do not qualifybecause each empty leaf node has its own location soif you want to use flyweightyou must pass in coordinates another design choice iswho controls the workthe node class or the tree classfor exampleon an insert operationyou could have the tree class control the flow down the treelooking at (queryingthe nodes to see their type and reacting accordingly this is the approach used by the bst implementation in section an alternate approach is to have the node class do the work that isyou have an insert method for the nodes if the node is internalit passes the city record to the appropriate child (recursivelyif the node is flyweightit replaces itself with