Problem
1. A binary tree with n nodes has 1 external node, what is the height of this tree? Briefly justify.
2. n = 20561. Now consider a full binary tree with n nodes. What is the number of internal nodes and external nodes in this tree?
3. For k ≥ 3, a complete binary tree has 2 k - 3 nodes. How many external nodes does it have as a function of k? Briefly justify.
4. How many full binary trees exist with 7 nodes? How many of them are perfect? Draw them.
5. A binary tree contains letters on the nodes which are printed when the node is visited during tree traversals. Below is the result for two of these traversals on the same tree:
In-order traversal: I E A H J D F B C G
Post-order traversal: I A J F D H E G C B
Give the pre-order traversal of this tree.