Four words describe the shape of a binary tree:
- full — every node has 0 or 2 children;
- complete — every level is filled, except possibly the last, which is filled from the left;
- perfect — every level is completely filled (2ʰ − 1 nodes for height h);
- degenerate — no node has two children: the tree is a linked list in disguise.
Write TreeKinds: each line of the input is a list of keys to insert in an empty BST. For each line, print the number of nodes, the height and the four answers. isFull and isDegenerate are recursive, isPerfect uses size and height, and isComplete uses a breadth-first traversal: in level order, no node may appear after a missing child. For the input
4 2 6 1 3 5 7
4 2 6 1 3
4 2 6 5 7
1 2 3 4
4 2 6 1
5
3 1 2
the program prints
Keys 4 2 6 1 3 5 7: 7 nodes, height 3
full true, complete true, perfect true, degenerate false
Keys 4 2 6 1 3: 5 nodes, height 3
full true, complete true, perfect false, degenerate false
Keys 4 2 6 5 7: 5 nodes, height 3
full true, complete false, perfect false, degenerate false
Keys 1 2 3 4: 4 nodes, height 4
full false, complete false, perfect false, degenerate true
Keys 4 2 6 1: 4 nodes, height 3
full false, complete true, perfect false, degenerate false
Keys 5: 1 nodes, height 1
full true, complete true, perfect true, degenerate true
Keys 3 1 2: 3 nodes, height 3
full false, complete false, perfect false, degenerate true