the height of binary tree binary trees don' have simple relation between their size and height the maximum height of binary tree with nodes is ( )which happens when all non-leaf nodes have precisely one childforming something that looks like chain on the other handsuppose we have nodes and want to build from them binary tree with minimal height we can achieve this by 'fillingeach successive level in turnstarting from the root it does not matter where we place the nodes on the last (bottomlevel of the treeas long as we don' start adding to the next level before the previous level is full terminology variesbut we shall say that such trees are perfectly balanced or height balanced and we shall see later why they are optimal for many of our purposes basicallyif done appropriatelymany important tree-based operations (such as searchingtake as many steps as the height of the treeso minimizing the height minimizes the time needed to perform those operations we can easily determine the maximum number of nodes that can fit into binary tree of given height calling this size function ( )we obtainh ( in factit seems fairly obvious that ( + this hypothesis can be proved by induction using the definition of binary tree as follows(athe base case applies to the empty tree that has height - which is consistent with (- - + nodes being stored (bthen for the induction stepa tree of height has root node plus two subtrees of height by the induction hypothesiseach subtree can store ( + nodesso the total number of nodes that can fit in height tree is ( + + ( + )+ ( it follows that if (his correct for the empty treewhich it was shown to be in the base case abovethen it is correct for all an obvious potential problem with any proof by induction like thishoweveris the need to identify an induction hypothesis to start withand that is not always easy another way to proceed here would be to simply sum the series ( algebraically to get the answer sometimeshoweverthe relevant series is too complicated to sum easily an alternative is to try to identify two different expressions for ( as function of ( )and solve them for (hheresince level of tree clearly has nodeswe can explicitly add in the + nodes of the last level of the height tree to give ( ( + alsosince height tree is made up of root node plus two trees of height ( (hthen subtracting the second equation from the first gives ( +