Dailey's Numbers

In this assignment you are to implement your own binary tree to compute Dailey's Numbers
The first the numbers in the sequence are: 1 2 3

Start a tree rooted at 3

The left node of a branch is computed as the sum of the parent and parent's grandparent.
The right child of a node is computed as the sum of the parent and parent's parent.

The user will enter an integer between 2 and 26 that you are to use as the tree depth.

A depth of 1 is only the root 3
A depth of 5:
Depth of 6
Traversals

Provide a menu interface so that the user can select preorder, inorder, or post order traversal of the tree.
Output the selected order
Place this menu in a loop so the user can repeatedly select an order

Missing numbers and Repeats
Determine the numbers that are missing from the tree from 1 to the value in the rightmost leaf of the tree

For each number in the tree, determine how may times it appears in the tree

For a tree of depth 6, this is the correct answer: 

Missing: 23 28 32 33
Counts
1: 1
2: 1
3: 1
4: 1
5: 1
6: 1
7: 2
8: 1
9: 1
10: 3
11: 2
12: 1
13: 2
14: 2
15: 3
16: 2
17: 3
18: 2
19: 3
20: 1
21: 3
22: 4
23: 0
24: 7
25: 2
26: 4
27: 4
28: 0
29: 3
30: 1
31: 2
32: 0
33: 0
34: 1
Submission
Place your code in the D2L dropbox
Place a text document of your output for input of 25 in the D2L dropbox