How many binary search trees can be made with 36 nodes that the difference between depth of the leaves is at most 1?

Question

I am looking at this challenge:

How many binary search trees can be made with 36 nodes such that the difference between the depths of the leaves is at most one?

Can I say that it also means that How many perfectly balanced binary trees can be made with 36 nodes?

Will these two questions mean the same?

Answer 1

Can I say that it also means that How many perfectly balanced binary trees can be made with 36 nodes? Will these two questions mean the same?

Yes, because once the shape of the binary tree is fixed, there is only one way to label the nodes with numbers 1.. so that it is also a BST.

As the depths of the leaves can only differ by 1, the tree is as most balanced as it can be. The height of the tree must therefore be ⌊log₂36⌋, i.e. 5. The top 31 nodes of the tree form a perfect binary tree, with height 4 (i.e. 5 levels):

               ┌───────────────○───────────────┐
       ┌───────○───────┐               ┌───────○───────┐ 
   ┌───○───┐       ┌───○───┐       ┌───○───┐       ┌───○───┐   
 ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐
 ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○

There are now 5 more nodes to append at the bottom of the tree, and there are 32 "slots" (nulls) in the level below the depicted tree where they could be placed. For instance, this is one of those:

               ┌───────────────○───────────────┐
       ┌───────○───────┐               ┌───────○───────┐ 
   ┌───○───┐       ┌───○───┐       ┌───○───┐       ┌───○───┐   
 ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐
 ○   ○  ┌○   ○   ○   ○┐  ○  ┌○┐  ○   ○  ┌○   ○   ○   ○   ○   ○
        ○             ○     ○ ○         ○

So we need to count the number of ways to choose 5 out of 32, i.e. ₃₆₅, which is:

₃₆₅ = 36! / (5! 31!) = 376992