This week's giveaway is in the Android forum. We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line! See this thread for details.

Does anyone know an algorithm or have a pseudo code that they could post that would allow me to check if a Binary Tree is a perfect tree? A perfect binary tree is defined as a full binary tree of height n with exactly (2^n)-1 nodes. (A full binary tree is one where every node has either 2 or 0 children).

The way folks here prefer to work is for you to take your best shot and then ask for questions about the parts that are giving you trouble, or ask for a review of anything you're not sure about.

Since you apparently know the definition of a perfect tree, you should be able to write down the very simple, precise steps in English that one would use to do this "manually". That is one form of pseudocode. Since pseudocode is not any specific, formal language, you can call that your pseudocode, or if you want something that's a little more rigid and closer to what your real code will ultimately look like, you can start with the English steps and refine them to a more "code-like" but still syntactically informal form.

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76

posted

0

I already have code working out but it wont pass all my test cases.

William Koch wrote:I already have code working out but it wont pass all my test cases.

So what exactly is the problem? You need to TellTheDetails(←click) to make it easier for people to understand what's not working.

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76

posted

0

The problem is this JUnit test case will not pass. The tree is defined like this (there are 3 parts; the first part is the element in the node, the second part is the left child and the third part is the right child:

William, there is a difference between perfect binary tree and fully binary tree.

perfect binary tree : every node should contain exactly 2 childs(except leaf nodes) and all leaf nodes should be at same level
fully binary tree: every node has exactly 0 or 2 childs.

here you are trying to identify a binary tree is perfect or not right? see the properties of perfect binary tree . one property is that
size = (2 power (h+1)) - 1 ;
size = number of nodes and h=height of that tree. now you can write a program that validate above equation.

William Koch wrote:The problem is this JUnit test case will not pass. The tree is defined like this (there are 3 parts; the first part is the element in the node, the second part is the left child and the third part is the right child:

This is extremely difficult to read. Does your Tree class have an addChild method? If so, consider using that instead of all these perplexing nested instantiations.

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76

posted

0

Sorry it is difficult indeed to read but I did not create it. Here is the tree class

And I did get the solution. Instead it need to be size = 2^(n+1) - 1 it is just (2^n) -1 where n is the height of the tree. The size and height methods are below as well