methods size(and isempty(use an instance variable storing the number of nodes of tand each take ( time the accessor methods rootleftrightsibling and parent take ( time method replace( ,etakes ( time methods iterator(and positions(are implemented by performing preorder traversal of the tree (using the auxiliary method preorderpositionsthe nodes visited by the traversal are stored in position list implemented by class nodepositionlist (section and the output iterator is generated with method iterator(of class nodepositionlist methods iterator(and positions(take (ntime and methods hasnext(and next(of the returned iterators run in ( time method children uses similar approach to construct the returned iterable collectionbut it runs in ( timesince there are at most two children for any node in binary tree the update methods insertleftinsertrightattachand remove all run in ( timeas they involve constant-time manipulation of constant number of nodes considering the space required by this data structure for tree with nodesnote that there is an object of class btnode (code fragment for every node of tree thusthe overall space requirement is (ntable summarizes the performance of the linked structure implementation of binary tree table running times for the methods of an nnode binary tree implemented with linked structure methods hasnext(and next(of the iterators returned by iterator()positions(iterator()and children(viterator(run in ( time the space usage is (noperation time sizeisempty ( iteratorpositions