William Koch

Ranch Hand

Posts: 76

posted 4 years ago

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).

posted 4 years ago

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.

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.

posted 4 years ago

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

posted 4 years ago

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:

The test case is this:

posted 4 years ago

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.

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

posted 4 years ago

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