+ < <= + - + <= <= <= <= - log( < <( )/ relating internal nodes to external nodes in proper binary tree in addition to the binary tree properties abovewe also have the following relationship between the number of internal nodes and external nodes in proper binary tree proposition in nonempty proper binary tree twith external nodes and internal nodeswe have justificationwe justify this proposition by removing nodes from and dividing them up into two "piles"an internal-node pile and an external-node pileuntil becomes empty the piles are initially empty at the endthe externalnode pile will have one more node than the internal-node pile we consider two casescase if has only one node vwe remove and place it on the external-node pile thusthe external-node pile has one node and the internal-node pile is empty case otherwise ( has more than one node)we remove from an (arbitraryexternal node and its parent vwhich is an internal node we place on the external-node pile and on the internal-node pile if has parent uthen we reconnect with the former sibling of was shown in figure this operationremoves one internal node and one external nodeand leaves the tree being proper binary tree repeating this operationwe eventually are left with final tree consisting of single node note that the same number of external and internal nodes have been removed and placed on their respective piles by the sequence of operations leading to this final tree nowwe remove the node of the final tree and we place it on the external-node pile thusthe the external-node pile has one more node than the internal-node pile