PROBLEM 2: Define a node of a binary tree to be full if it has both a left and a right child.

Prove by induction that the number of full nodes in any non-empty binary tree is 1 fewer than the number of leaves (number-of-full-nodes = (number-of-leaves - 1))

Some examples given below.

PROBLEM 2: A complete binary tree of height h has exactly 2^h+1-1 nodes.

In a ternary tree, nodes can have up to 3 children. Prove by induction that a complete ternary tree of height h has exactly nodes for all h 0.

Examples:

#Full-Nodes: #Leaves: 1 0 #Full-Nodes: #Leaves: 1 0 #Full-Nodes: #Leaves: 2 #Full-Nodes: #Leaves: 2 1 1