An algorithm that checks if a tree is complete and complete
I'm trying to write a method that will return true if the binary tree is complete and complete (each node has 2 childern or none and all the leaves of the tree are at the same depth).
My idea is to use recursion. I will check any node, if he left a son, has a childern number, that euqals to him on the right of a son, a childern number. If so, I will return true, otherwise false;
The algorithm will look like this:
public class Utils {
public boolean isFullCompleteTree(Tree<Integer> t) {
TreeInfo rootInfo = isFullCompleteTree(t.getRoot());
return rootInfo.valid;
}
public TreeInfo isFullCompleteTree(Node<Integer> node) {
boolean valid = true;
if (node == null) {
return new TreeInfo(true, 0);
}
TreeInfo rightInfo = isFullCompleteTree(node.goRight());
TreeInfo leftInfo = isFullCompleteTree(node.goLeft());
if ((!rightInfo.valid) || (!leftInfo.valid)) {
valid = false;
}
if (rightInfo.numChildern != leftInfo.numChildern) {
valid = false;
}
return new TreeInfo(valid, rightInfo.numChildern + leftInfo.numChildern
+ 1);
}
}
class TreeInfo {
public boolean valid;
public int numChildern;
public TreeInfo(boolean valid, int numChildern) {
this.valid = valid;
this.numChildern = numChildern;
}
}
I haven't implemented the tree implementation, but it's pretty simple.
The idea of the algorithm is to check whether each
Do you think my alogrithem is a proofreader or am I missing something?
Many thanks.
source to share
I think you are asking for a more mathematical proof of your algorithm. Your algorithm is correct. The proof can be done simply by subtraction.
Lemma 1:
If a complete and complete binary tree has the number of nodes equal N
, then it leaves the depthlog2(N+1)
This lemma itself can be proved by the following conclusion:
For N = 1
this is correct.
For N > 1
its left and right subtrees have (N-1)/2
nodes and both have their leaves depth = log2((N-1)/2+1)
, so now the depth will belog2((N-1)/2+1) + 1 = log2(((N-1)/2+1) * 2) = log2(N-1 + 2) = log2(N+1)
By your definition, "full and complete" means "each node has 2 children or none, and all the leaves of the tree are at the same depth"
So, if both subtrees are "full and complete" and they have the same number of nodes (say this M
), then all leaves in both subtrees will have the same , and their depth in the original tree will be . Lemma 1
depth = log2(M+1)
log2(M+1) + 1
And also the root has 2 children, plus both "full and full" subtrees mean that all notes have 2 children or not. Then, by definition, the original tree is also "complete and complete".
Again, as fge @ mentioned, this can be done much easier. How easy is it to check if max depth == log2 (N-1)
source to share