Assignment:
Recall that a binary tree can be defined recursively as:
* A Binary Tree is either empty
* or A Binary Tree consists of a node with a left and right child both of which are Binary Trees.
The degree of a node in a tree is equal to 0 if both children are empty, 1 if one of the children are empty, and 2 of both children are not empty. Use induction to show that the number of nodes in a binary tree is equal to one more than the sum of the degrees of the nodes in a binary tree.
Provide complete and step by step solution for the question and show calculations and use formulas.