logo CodeStepByStep logo

Main Page → Exercises → C++ → Solve an Exercise

completeToLevel

Language/Type: C++ binary trees pointers recursion

Write a function named completeToLevel that accepts a reference to a pointer to the root of a binary tree of integers. Your function should also accept an integer K as a parameter and adds nodes with value -1 to a tree so that the first K levels are complete. A level is complete if every possible node at that level is non-nullptr. 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. You must implement your function recursively and without using loops.

root after completeToLevel(root, 3); 
(17 (83 (19 / (48))) (6 / (87 (75) /)))

(17 (83 (19 / (48)) (-1)) (6 (-1) (87 (75)))

Constraints: Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc).

Assume that you are using the BinaryTreeNode structure as defined below: 

struct BinaryTreeNode {
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};
Function: Write a C++ function as described, not a complete program.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.