log ( log in which the approximation is valid for large hence perfectly balanced tree consisting of nodes has height approximately log this is goodbecause log is very smalleven for relatively large nn log we shall see later how we can use binary trees to hold data in such way that any search has at most as many steps as the height of the tree thereforefor perfectly balanced trees we can reduce the search time considerably as the table demonstrates howeverit is not always easy to create perfectly balanced treesas we shall also see later the size of binary tree usually binary tree will not be perfectly balancedso we will need an algorithm to determine its sizei the number of nodes it contains this is easy if we use recursion the terminating case is very simplethe empty tree has size otherwiseany binary tree will always be assembled from root nodea left sub-tree land right sub-tree rand its size will be the sum of the sizes of its componentsi for the rootplus the size of lplus the size of we have already defined the primitive operator isempty(tto check whether binary tree is emptyand the selectors left(tand right(twhich return the left and right sub-trees of binary tree thus we can easily define the procedure size( )which takes binary tree and returns its sizeas followssize(tif isempty(treturn else return ( size(left( )size(right( ))this recursively processes the whole treeand we know it will terminate because the trees being processed get smaller with each calland will eventually reach an empty tree which returns simple value implementation of trees the natural way to implement trees is in terms of records and pointersin similar way to how linked lists were represented as two-cells consisting of pointer to list element and pointer to the next two-cell obviouslythe details will depend on how many children each node can havebut trees can generally be represented as data structures consisting of pointer to the root-node content (if anyand pointers to the children sub-trees the inductive definition