wood burning stoves 2.0*
The moose likes Java in General and the fly likes Pseudo Code for isPerfectTree() method Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Pseudo Code for isPerfectTree() method" Watch "Pseudo Code for isPerfectTree() method" New topic
Author

Pseudo Code for isPerfectTree() method

William Koch
Ranch Hand

Joined: Sep 26, 2012
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

Joined: Jan 03, 2004
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

Joined: Sep 26, 2012
Posts: 76
I already have code working out but it wont pass all my test cases.

Here is what I have:

Jeff Verdegan
Bartender

Joined: Jan 03, 2004
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

Joined: Sep 26, 2012
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

Joined: Jan 28, 2008
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

Joined: Mar 12, 2011
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

Joined: Sep 26, 2012
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







 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: Pseudo Code for isPerfectTree() method