logo CodeStepByStep logo


Language/Type: C++ binary trees pointers recursion
Related Links:
Author: Marty Stepp (on 2016/08/27)

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.

root after completeToLevel(root, 3);
(17 (83 (19 / (48)) /) (6 / (87 (75) /)))
(17 (83 (19 / (48))) (6 / (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;
Type your C++ solution code here:

This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.

Log In

Need help?

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.