root nil nil nil nil nil nil nil nil nil nil nil nil fig tree of fig represented as linked data structure before investigating how trees might be used advantageously and how to perform operations on treeswe give an example of how tree may be constructed by program assume that tree is to be generated containing nodes with the values of the nodes being numbers read from an input file in order to make the problem more challenginglet the task be the construction of tree with nodes and minimal height in order to obtain minimal height for given number of nodesone has to allocate the maximum possible number of nodes of all levels except the lowest one this can clearly be achieved by distributing incoming nodes equally to the left and right at each node this implies that we structure the tree for given as shown in fig for = = = = = = = fig perfectly balanced trees the rule of equal distribution under known number of nodes is best formulated recursively use one node for the root generate the left subtree with nl div nodes in this way generate the right subtree with nr nl nodes in this way the rule is expressed as recursive procedure which reads the input file and constructs the perfectly balanced tree we note the following definitiona tree is perfectly balancedif for each node the numbers of nodes in its left and right subtrees differ by at most type node pointer to record (adens _balancedtree *