Learn the essential functions of CompTIA Security+, which establishes the core knowledge required of any cybersecurity role and leads professionals into intermediate-level cybersecurity jobs.

i have a binary tree. I can count the nodes,add,delete, and check to see if it is full, but what i cannot figure out is how to check to see if it is complete

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get this solution by purchasing an Individual license!
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Note that this problem is really only hard if you are storing your binary tree using pointers in the traditional manner. If you store your binary tree in an array it is easy to check the index of the last child and the number of children. They will match in a complete tree.

So, back to the hard one: The left subtree must be full (if there are enough leaves in the bottom tier) or it must be complete. The left subtree must be full (if there are too few nodes to spill over in the last row) or it must be complete. Thus we have a recursive relationship between a complete tree and its left and right subtrees.

Yeah!

Hope this helps (ask if you don't understand what I said).

-bcl

(1) The recursive relationship I described above holds from the root down. That is you call either full or complete on the left and right subtrees and return the and of the two values.

(2) I thought of an alternative algorithm:

do a breadth first traversal of the whole tree.

store an integer in each node in the tree indicating the order in which it was visited

in the depth first traversal (root node is 0).

do an in-order (order doesn't matter here) traversal and check at each node that:

both subtrees are empty or the right subtree is empty

if a subtree is not empty:

if its a left subtree the node number should be 2 * n + 1 where n is the number of the current node

if it is a right subtree the node number should be 2 * n + 2.

Maps the array storage mechanism onto the pointer based binary tree.

Hope this helps, -bcl

complete(nodePtr curr) {

if (!curr) return true;

n = sizeOfTree(curr);

h = heightOfTree(curr);

if (h > floor(logbase2(n)) + 1) return false; // too tall to work

// If it IS a complete tree we know the bottom row must be populated from the left

// the question is where do those nodes end? Do they go more than halfway across?

// How would we know if they went more than halfway across? Well we can remove the

// nodes in the "full" part of the tree from consideration and then see:

f = nodesInAFullTree(h-1);

k = n - f; // nodes in the last row

if (k > f / 2) // why?

return full(curr->left) && complete(curr->right);

else

return complete(curr->left) && full(curr->right);

(Note I haven't compiled and tested this code and there could be off by 1 errors in the comparisons).

-bcl

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialOkay, there are a couple of missing checks in the recursive version:

return false if

- size of left subtree is less than size of right subtree

- height of left subtree is less than height of right subtree

- height of left subtree is more than one greater than height of right subtree

With those tests in the two find all of the complete trees for tree sizes up to 12 nodes (I ran them across all permutations of insertion order into the bst; not the most efficient testing regime but it is exhaustive).

So, again, what is the deal with posting the question again and giving my a lousy grade? I believe I answered the question.

-bcl

C++

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get this solution by purchasing an Individual license!
Start your 7-day free trial.

"A complete binary tree has 2k nodes at every depth k < n and between 2n and 2n+1-1 nodes altogether"