2
$\begingroup$

With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that:

  • Exactly $1$ leaf node(s) present?
  • Exactly $2$ leaf nodes present?

I was able to solve the first one(and the actual problem was also that, but then I though what if the process can be extended)

Here's my take on the 1st one

Here the elements are  $1,2,3,4,5,6,7$ (let's assume that for simplicity) and we need only $1$ leaf 

  • So let us fix a root node: To fix the root node we have $2$choice either $1$ or $7$ from  $1,2,3,4,5,6,7$

  • (if we select any non-extreme elements then only $1$ leaf is not possible)

  • Let us say we select $1$ as root node 

  • In each and every level we have $2$ different option that is to select i,e; either of extreme elements

  • So in 2nd level we can select $2,3,4,5,6,7$

  • Let us say we select $7$ in 2nd level 

  • We still have 2 option to select in $2,3,4,5,6$

  • So this is true in all levels except last level since only $1$ element is left.

  • Therefore, total possibilities are : $2 * 2 * 2 * 2 * 2$ = $2^5$

The same condition is true for $7$ as a root

Hence, $2^5* 2$ (1 as root or 7 as root)  =  $2^6$.

(Which comes out as $2^{number of nodes -1}$)

But how can we now approach the second subpart or it can be generalized for let's say (2,3,4) leaf nodes?

  • Exactly 2 leaf nodes present?
$\endgroup$
2
$\begingroup$

You can compute the numbers with dynamic programming.

Let $c(n,l)$ be the number of BSTs with $n$ nodes and $l$ leaves, where the nodes are selected from a set of $n$ distinct nodes. Then we have the following recurrence relation in general cases,

$$c(n,l) = \sum_{i=0}^{n-1}\sum_{j=0}^l c(i,j)\cdot c(n-i-1, l-j)$$

  • The outer summation is over $i$, the number of nodes in the left sub-BST of a BST with $n$ nodes and $l$ leaves.
  • The inner summation is over $j$, the number of leaves in the the left sub-BST of $i$ nodes.
  • The product $c(i,j)\cdot c(n-i-1, l-j)$ is the number of BSTs whose left sub-BST has $i$ nodes and $j$ leaves and whose right sub-BST has $n-i-1$ nodes and $l-j$ leaves. Please note that the root of such BST has only one choice, namely, the $(i+1)^{th}$ smallest node.

I will let you figure out the boundary values of $c(n,l)$ such as when $n=0$ or $n=1$ or $l=0$. There might be a few different cases. However, this should be enough to point you to the right direction.

$\endgroup$
  • $\begingroup$ Hey Thanks for your wonderful answer! I am not sure I got it completely, this line bugs me <the root of BST has only one choice> That's means it's valid for both left sub BST and right sub-BST right? $\endgroup$ – Aditya Nov 1 '18 at 4:54
  • 1
    $\begingroup$ By the statement, I mean if the left subtree has $i$ nodes, the root must be the $(i+1)^{th}$ smallest node ( and the right subtree must have $n-i-1$ nodes. $\endgroup$ – Apass.Jack Nov 1 '18 at 4:56
  • $\begingroup$ In a binary search tree, the root node is smaller than or equal to every node in its left subtree. The root node is greater than or equal to every node in its right subtree. So its left subtree and right subtree are symmetric. I do not get why you say "it only applies to the right sub bst and not to the left ones". Can you write in full detail what is that "it"? $\endgroup$ – Apass.Jack Nov 1 '18 at 5:01
  • $\begingroup$ Oh I got your point now(I was confused about that line meaning).. Thanks for the clarifications and for your quick reply. $\endgroup$ – Aditya Nov 1 '18 at 5:04
  • 1
    $\begingroup$ Oh, I see why you were confused. I could have also said, "... or, what is equivalent, its $(n-i)^{th}$ largest element" to keep the symmetry. $\endgroup$ – Apass.Jack Nov 1 '18 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.