Solved

how do i check to see if a binary tree is complete

Posted on 2003-12-10
9
592 Views
Last Modified: 2010-04-01
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
0
Comment
Question by:Azrael1o
  • 5
  • 3
9 Comments
 
LVL 86

Expert Comment

by:jkr
ID: 9915909
See the definition at http://www.nist.gov/dads/HTML/completeBinaryTree.html - you have to check whether this requirement is met:

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

Author Comment

by:Azrael1o
ID: 9915950
That i understand. and i also know that i should do it recursively but i cannot figure out code or even psydo code to check this
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9915996
What is the definition of a complete binary tree? One that is full down to heigh - 1, right? So you can check for that with a modified full check (one that takes a max depth to check). The other requirement is harder: all nodes in the bottom row are as far to the left as possible.

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
0
 

Author Comment

by:Azrael1o
ID: 9916455
I think i understand what your saying..but do u start checking from the beginning or from the bottom and and how would you do that recursively?
0
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 
LVL 11

Expert Comment

by:bcladd
ID: 9916738
I was thinking about this on the drive home.

(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
0
 

Author Comment

by:Azrael1o
ID: 9916830
I like the 1 recursive idea.  But i dont fully understand it. i understand that you check each not to see weather or not it has 2 children. would you return false if it doesnt have 2 children and its not the next to last row?(i do have a function to count the height so that should help)
0
 
LVL 11

Accepted Solution

by:
bcladd earned 500 total points
ID: 9916908
The following is not the most effecient algorithm in the universe (but I can think of several ways to speed it up by caching results of some of the funcitons):

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
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9933920
Why a C? I provided two different approaches to the problem.

-bcl
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9934623
And both algorithms actually work. (Just wrote a quick test.)

Okay, 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
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now