induction stepgiven tree with internal nodesselect an internal node whose children are both leaf nodes remove both of ' childrenmaking leaf node call the new tree has internal nodes from the induction hypothesist has leaves nowrestore ' two children we once again have tree with internal nodes how many leaves does havebecause has leavesadding the two children yields + howevernode counted as one of the leaves in and has now become an internal node thustree has leaf nodes and internal nodes by mathematical induction the theorem holds for all values of > when analyzing the space requirements for binary tree implementationit is useful to know how many empty subtrees tree contains simple extension of the full binary tree theorem tells us exactly how many empty subtrees there are in any binary treewhether full or not here are two approaches to proving the following theoremand each suggests useful way of thinking about binary trees theorem the number of empty subtrees in non-empty binary tree is one more than the number of nodes in the tree proof take an arbitrary binary tree and replace every empty subtree with leaf node call the new tree all nodes originally in will be internal nodes in (because even the leaf nodes of have children in is full binary treebecause every internal node of now must have two children in and each leaf node in must have two children in (the leaves just addedthe full binary tree theorem tells us that the number of leaves in full binary tree is one more than the number of internal nodes thusthe number of new leaves that were added to create is one more than the number of nodes in each leaf node in corresponds to an empty subtree in thusthe number of empty subtrees in is one more than the number of nodes in proof by definitionevery node in binary tree has two childrenfor total of children in tree of nodes every node except the root node has one parentfor total of nodes with parents in other wordsthere are non-empty children because the total number of children is nthe remaining children must be empty binary tree node adt just as we developed generic list adt on which to build specialized list implementationswe would like to define generic binary tree adt based on those