Minimum number of nodes in AVL tree given that the shallowest leaf is at level k

Question

My teacher asked this quesion in class, to find the minumum number of nodes in an AVL tree where the depth of the nearest leaf is K. But there is a catch, like we have to do it in O(1) time and not a recursive formulartion.

My approach is like this: For minimum number of nodes, the height of the tree also needs to be k(where k is the depth of the nearest leaf node). But after concluding this, the only approach that is coming to me is the recursive approach for minimum number of nodes in a AVL tree of height h,i.e., N(h) = N(h-1) + N(h-2) +1, with N(0)=0 and N(1) = 1. But my prof asked not to do it recursively and rather give a O(1) solution for this. Is it possible? If so can anyone please share some hints.

Answer 1

For minimum number of nodes, the height of the tree also needs to be k (where k is the depth of the nearest leaf node).

Yes, this is the correct approach.

By consequence, all root-to-leaf paths have length . If there would be a shorter path, then the nearest leaf node has a depth less than , and if there would be a longer path, the height of the tree would be more than .

In other words, all leaf nodes are at the bottom level of the tree. For instance, this is the case with a perfect binary tree.

We can however remove some leaves from a perfect binary tree without breaking the conditions, i.e. without reducing the height of the tree, and without creating new leaves (which would have less depth than ).

Example of a perfect tree (=3):

                    _____ 8 _____
                   /             \
                _ 4 _          _ 12 _
               /     \        /      \
              2       6      10      14
             / \     / \    /  \    /  \
            1   3   5   7  9   11  13  15

We can remove half of the leaves without creating new ones, nor breaking the AVL property, nor reducing the height:

                    _____ 8 _____
                   /             \
                _ 4 _          _ 12 _
               /     \        /      \
              2       6      10      14
             /       /      /       /   
            1       5      9       13

We cannot remove more nodes without breaking one of the requirements.

The characteristic of this "minimal" tree is that it is a perfect tree of height −1 where each leaf gets a single child attached to it (it doesn't matter whether that is a left or right child).

How many nodes does such a tree have?

A perfect tree of height −1 has 2−1 nodes. It has 2⁻¹ leaves. For each of those we have to count an extra node (to create the bottom level) so that in total we have 2−1 + 2⁻¹ nodes, or otherwise put: 3∙2⁻¹−1. For =0 (a single node), the answer is just 1.

As code:

k > 0 ? (3<<(k-1))-1 : 1