(dthe records arrive with values having uniform random distribution (so the bst is likely to be well balanced insertions are performedfollowed by , , searches projects re-implement the composite design for the binary tree node class of figure using flyweight in place of null pointers to empty nodes one way to deal with the "problemof null pointers in binary trees is to use that space for some other purpose one example is the threaded binary tree extending the node implementation of figure the threaded binary tree stores with each node two additional bit fields that indicate if the child pointers lc and rc are regular pointers to child nodes or threads if lc is not pointer to non-empty child ( if it would be null in regular binary tree)then it instead stores pointer to the inorder predecessor of that node the inorder predecessor is the node that would be printed immediately before the current node in an inorder traversal if rc is not pointer to childthen it instead stores pointer to the node' inorder successor the inorder successor is the node that would be printed immediately after the current node in an inorder traversal the main advantage of threaded binary trees is that operations such as inorder traversal can be implemented without using recursion or stack re-implement the bst as threaded binary treeand include non-recursive version of the preorder traversal implement city database using bst to store the database records each database record contains the name of the city ( string of arbitrary lengthand the coordinates of the city expressed as integer xand -coordinates the bst should be organized by city name your database should allow records to be inserteddeleted by name or coordinateand searched by name or coordinate another operation that should be supported is to print all records within given distance of specified point collect running-time statistics for each operation which operations can be implemented reasonably efficiently ( in th(log ntime in the average caseusing bstcan the database system be made more efficient by using one or more additional bsts to organize the records by location create binary tree adt that includes generic traversal methods that take visitoras described in section write functions count and bstcheck of section as visitors to be used with the generic traversal method