CODEWITHSUNDEEP
data-structurestreebinary-treeavl-tree
Jasmine
Jasmine

Reputation: 49

How many maximum height AVL trees given height?

I am having some trouble finding a recursive formula for finding the number of maximum height AVL trees of height h. Height 0 has 1, height 1 has 2, height 2 has 4, height 3 has 8, etc. is that correct?

Upvotes: 2

Views: 1640

Answers (2)

Lrrr
Lrrr

Reputation: 4817

Let look at this problem from another point of view.

Instead of maximum height for a given count of nodes, let find the minimum number of nodes for a given height. For this problem, we have this recursive function: n(h) = n(h-1) + n(h-2) + 1 because you need at least n(h-1) nodes in right subtree and n(h-2) nodes in left subtree and one node for root.

AVL Tree (image and more complete explanation here).

With that in mind, you have to find an h such that n(h) < n < n(h+1) where n is your given number of nodes.

By the way the short answer is h < 2log(n) + 2

Upvotes: 1

karastojko
karastojko

Reputation: 1181

The maximum number of nodes n in AVL tree of height h is n = 2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1 (each node except the root has both children, meaning that each level has twice more nodes than the previous one). That gives the formula of height h in terms of number of nodes n as: h = log(n + 1).

Upvotes: 0

Related Questions