In a Number Tree puzzle, you must enter the numbers from 1 to Nonce each (for a puzzle with N circles), such that each non-leaf ofthe tree contains the sum of the numbers that it is connected tofrom above. The root and usually at least one other circle havenumbers given to you, as shown in the example above.

For clarification:

- In the case where some circles have given numbers, thosenumbers do count toward the use of each number once.
- The root node need not have a value between 1 and N.
- In the description above, “above” refers to the diagram. Noticethat in the diagram, the leaves are “up” and the root node is”down”.

Complete the NumberTree class described below:

int size() const

Return the number of nodes in the tree.

int height() const

Return the height of the tree.

void load(const string& str)

Initialize a NumberTree from a string.

- The string will contain one line for each node.
- Each line is terminated by a semi-colon.
- The semi-colon after the last line is optional.
- The first token in each line is the name of the node.
- Remaining tokens identify the node’s children.
- If a node’s “name” is a number, than that node’s value is fixed(e.g., node “4” above).
- A non-numerical node must begin with a character. (In otherwords, “1st” isn’t a valid node name.)
- You may assume the input lists child nodes before theparent.
- Raise an invalid_argument exception if the input is not valid(doesn’t parse, nodes are out of order, node repeated, number isout of range, orphan node, etc.)

Sample Input:

ABCD4 A BE D 4F 4 BG B C19 E F G

bool verify(const string& str) const;

Verify that the content of str represents a valid solution tothe problem. The input str describes the values to be placed in theempty nodes. Verify that those values satisfy the puzzle.Specifically:

- Each node’s value is equal to the values of its children.
- Each value between 1 to N is used exactly once. (Remember, thisrestriction does not apply to the root, but does apply to nodeswhose values were fixed by the problem definition.)

The input str will consist of a sequence of node names andvalues separated by semi-colons. For example a 1; b 2; c 3;

Raise an invalid_argument exception if the input is not valid(doesn’t parse, unknown node referenced, node is missing a value,value is out of range, etc.)

**Important:** Notice that this method is const.That means this method can’t modify the NumberTree, only query it.Specifically, you need to store the solution values in a datastructure that’s local to the method. The benefit of this methodbeing const is that you can now verify multiple solutions withouthaving to “reset” the object.

unordered_map<string, int> solve() const;

Find a solution to the puzzle and return a map of node names tovalues. Return an empty map if no solution exists. You may findthis function helpful:www.cplusplus.com/reference/algorithm/next_permutation/. Noticethat this is a const function: It may not modify the NumberTreeobject.

Extra credit: Find a non-brute-force solution. In other words,find a solution that is more clever than just trying assignments ofvalues to nodes until it find one that works.

## Expert Answer

Answer to In a Number Tree puzzle, you must enter the numbers from 1 to N once each (for a puzzle with N circles), such that each …