CODEWITHSUNDEEP
algorithmcomputer-science
Dilon Duuuman
Dilon Duuuman

Reputation: 21

Number of ways to create an AVL Tree with n nodes and L leaf node

I'd like to know number of ways I can create a Balanced Binary Tree with n nodes and L leaf nodes .

also I know that n must be ( 2*L - 1 ) .

Upvotes: 2

Views: 2939

Answers (1)

masotann
masotann

Reputation: 911

A balanced binary tree is a tree such that given any node, the two subtrees of that node has their height differing by at most one. So the number of nodes is not necessarily 2^L -1. If a tree has 2^L-1 nodes, then it is by definition, a full binary tree. So to answer your question.. If order does matter.. there are (n choose 1) ways (or n ways) to choose the top node. Then since order does matter, there are (n-1 choose 2) choices to choose the children of that node. And so on so forth. So it would be (n choose 1) *(n-1 choose 2) * (n-3 choose 2) * .... until n = 1 or 0.

If order doesn't matter.. the top node is still the same. You'll still have (n choose 1) choices for the top node. For one of the children of that node, we have n-1 choices and after we choose that, we have n-2 choices for the other child. Then we continue until we run out of choices. So in this case there would be n*(n-1)*(n-2)... = n! ways

----Edit--- Actually I made a mistake. the number of total nodes is not necessarily 2^L -1. Given n nodes, the height of a tree is floor(lg(n)). The number of leaf nodes has no correlation to the total number of nodes in the tree.

Upvotes: 1

Related Questions