Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Pseudo Code for isPerfectTree() method

William Koch
Ranch Hand
Posts: 76
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).

Jeff Verdegan
Bartender
Posts: 6109
6
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
Posts: 76
I already have code working out but it wont pass all my test cases.

Here is what I have:

Jeff Verdegan
Bartender
Posts: 6109
6
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
Posts: 76
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:

The test case is this:

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
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.

dennis deems
Ranch Hand
Posts: 808
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
Posts: 76
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