I am trying to write a method that will return true if a binary tree is full and complete (each node has 2 children or none and all the leaves of the tree are at the same depth).
My idea is to use recursion. I will check for any node if its left son has number of children that is equal to its right son's number of children. If so, I will return true, otherwise false;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 I didn't include the tree implementation but it is pretty straightforward.
The idea of the algorithm is to check if in every node the number of right son's children is equal to the left son's children. If a tree is not full and complete, then in some node this rule will not apply.
Do you think that my alogrithmalgorithm is corretcorrect or am I missing something?
