Write a function named completeToLevel that accepts a reference to a pointer to the root of a binary tree of strings.
Your function should also accept an integer K as a parameter and adds nodes with value "??" to a tree so that the first K levels are complete.
A level is complete if every possible node at that level is non-null.
We will use the convention that the overall root is at level 1, its children are at level 2, and so on.
Preserve any existing nodes in the tree.
For example, if a variable called root points to the root of the tree below and you make the call of completeToLevel(root, 3);, you should fill in nodes to ensure that the first 3 levels are complete.
Notice that level 4 of the tree below is not complete after the call.
Keep in mind that you might need to fill in several different levels.
Your function should throw an integer exception if passed a value for K that is less than 1.
root |
after completeToLevel(root, 3); |
"Al"
/ \
"Bob" "Ken"
/ \
"Joe" "Ed"
\ /
"Sue" "Tom"
|
"Al"
/ \
"Bob" "Ken"
/ \ / \
"Joe" "??" "??" "Ed"
\ /
"Sue" "Tom"
|
Constraints:
You must implement your function recursively and without using loops.
Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc).
Assume that you are using the BinaryTreeNodeString structure as defined below:
struct BinaryTreeNodeString {
string str;
BinaryTreeNodeString* left;
BinaryTreeNodeString* right;
};
