Description

instructions 

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 non-leaf of the tree contains the sum of the numbers that it is connected to from above. The root and usually at least one other circle have numbers given to you, as shown in the example above. 

For clarification:

• In the case where some circles have given numbers, those numbers 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. Notice that 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 other words, "1st" isn't a valid node name.)
• You may assume the input lists child nodes before the parent.
• Raise an invalid_argument exception if the input is not valid (doesn't parse, nodes are out of order, node repeated, number is out of range, orphan node, etc.)

Sample Input:

A
B
C
D
4 A B
E D 4
F 4 B
G B C
19 E F G
    

bool verify(const string& str) const;

Verify that the content of str represents a valid solution to the problem. The input str describes the values to be placed in the empty 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, this restriction does not apply to the root, but does apply to nodes whose values were fixed by the problem definition.)

The input str will consist of a sequence of node names and values 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 data structure that's local to the method. The benefit of this method being const is that you can now verify multiple solutions without having to "reset" the object. 

unordered_map<string, int> solve() const;

Find a solution to the puzzle and return a map of node names to values. Return an empty map if no solution exists. You may find this function helpful:www.cplusplus.com/reference/algorithm/next_permutation/. Notice that this is a const function: It may not modify the NumberTree object.

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