Determine the Highest Level that is Full – Binary Search Tree

I have a project do and I have everything done except for where I need to find the highest level that has the maximum amount of nodes in it. This is the code that I have, but I can’t seem to figure out how to do this:

 public int fullLevel() {
    int height = 1;
    int count = 1;
    fullLevel(root, height, count);
    return height;
} 

private int fullLevel(Node temp, int height, int count) {
    int height2 = (int) Math.pow(2, height - 1);

    if (temp == null) {
        return 0;
    }
    if (count == height2 && temp.left != null && temp.right != null) {
        count = 0;
        return fullLevel(temp.right, count, height + 1) + fullLevel(temp.left, count, height + 1);
    } else if (count != height2) {
        return fullLevel(temp.right, count + 1, height) + fullLevel(temp.left, count + 1, height);
    } else {
        return height;
    }
}

The question asks: “Determine the highest level that is full, or, equivalently, has the maximum number of nodes for that level.” – Must use recursion. Thanks!

I’m not great at recursion so sorry in advance!

Answer

You’re on the right track in terms of comparing the number of actual children in each level with the number of possible children for that level. The ideal approach would be to perform a level-order traversal using a queue and return the tallest full level. However, since you’re stuck using recursion, the problem becomes one of maintaining count horizontally across recursive calls. A naive solution is to create a list of counts for each height, then return the last full level in that list.

An optimization is only recursing if both children are present–clearly, if a child is missing, it’s impossible to have a full level deeper in the tree and we can wrap up our search.

public static int fullLevel(Node root) {
    ArrayList<Integer> levelCounts = new ArrayList<>();
    levelCount(root, 0, levelCounts);

    for (int i = levelCounts.size() - 1; i >= 0; i--) {
        if ((int)Math.pow(2, i) == levelCounts.get(i)) {
            return i;
        }
    }

    return -1;
}

private static void levelCount(Node root, int height, ArrayList<Integer> levelCounts) {
    if (root != null) {
        if (height >= levelCounts.size()) {
            levelCounts.add(0);
        }

        levelCounts.set(height, levelCounts.get(height) + 1);

        if (root.left != null && root.right != null) {
            levelCount(root.left, height + 1, levelCounts);
            levelCount(root.right, height + 1, levelCounts);
        }
    }
}

Output is 2 (zero-indexed) for the following example tree:

       ____1____
      /          
    _2_        __3__
   /         /     
  4     5    6      _7_    <-- tallest full level
 /    /    /     /   
8   9 10   11  12 13   14

Try it!

Leave a Reply

Your email address will not be published. Required fields are marked *