Hi,
WBahn, i have improved on the previous tree diagram (post#17). I hope it would be clearer now.

Zulfi.

 

Okay. So far so good. Now, of those 30, which ones are binary search trees?

 

Hi,
Thanks for your feed back. I have found 7 bst:

1:

1 (root)
2 (R)
3(R)
----------
2:

1(root)
3(R)
2(L)


=============
3: WRONG
2(root)
1(L)
3(R)
----------------


4: WRONG
2(root)
3(R)
1(L)

==============


5:
3(root)
2(L)
1(L)
----------------------
6:
3(root)
1(L)
2(R)
---------------
7.
2 (root)
1(L) 3 (R)





=============
Kindly guide me about the remaining bst.

Zulfi.

 

Consider your #3

||2||
|1|||
||3||

Does that satisfy the conditions for a valid binary search tree?

 

Hi,
I got your point. This does not satisfy bst property. The entire left subtree should be less than 2. Same is true with #4.

This would further reduce the number of binary search trees.

Zulfi.

 

Hi,
I got your point. This does not satisfy bst property. The entire left subtree should be less than 2. Same is true with #4.

This would further reduce the number of binary search trees.

Zulfi.

Yes. So.... what are the valid binary search trees?

 

Hi,

BST are :

1 (root)
2 (R)
3(R)
----------
2:

1(root)
3(R)
2(L)

----------


3:
3(root)
2(L)
1(L)
----------------------
4:
3(root)
1(L)
2(R)
---------------
5:
2 (root)
1(L) 3 (R)

Zulfi.

 

Correct.

Now, as for a formula for how many BSTs there are for a collection of N distinct keys, that is best done recursively. Essentually what you ask is, given N distinct keys, how many different root nodes can I have? For each root node, how many different left/right child pairs can I create? For each pair, how many nodes are in each subtree? You then have a recursive relationship that you try to solve for. I don't know how cumbersome the bookkeeping becomes.

But if you now understand what is going on, you can quickly figure out how many BSTs there are for a small number of key values. For instance, how many are there for 5 key values?

Well, I can root the top level node in any one of the 5 distinct values, placing all values less that the root in the left subtree and all the values larger than the root in the right subtree. So the number of nodes in each subtree are:

0,4
1,3
2,2,
3,1
4,0

The number of distinct trees for each root choice is the product of the number of distinct left-child subtrees and the number of distinct right-child subtrees.

So if T(N) is the number of BSTs that can be made with N distinct nodes, then

T(5) = T(4)*T(0) + T(3)*T(1) + T(2)*T(2) + T(1)*T(3) + T(1)*T(4)

So now we just need the number of BSTs you can make with 4, 3, 2, 1, and 0 nodes, but we can use the same approach. Eventually, we will need T(0) and T(1). T(0)=1, since it will only be used when we don't have a particular child but we still have one way to represent it, namely no child. More obvious is that T(1) = 1.

So what about T(2), T(3) and T(4)?

T(2) = T(1)*T(0) + T(0)*T(1) = 1 + 1 = 2

T(3) = T(2)*T(0) + T(1)*T(1) + T(0)*T(2) = 2+1+2 = 5

T(4) = T(3)*T(0) + T(2)*T(1) + T(1)*T(2) + T(0)*T(3) = 5 + 2 + 2 + 5 = 14

T(5) = T(4)*T(0) + T(3)*T(1) + T(2)*T(2) + T(1)*T(3) + T(1)*T(4) = 14 + 5 + 4 + 5 + 14 = 42

 

Hi,
Thanks, i would try to understand this and then reply you.

Zulfi.

 

Hi,
I like this work but i cant understand some thing.
Its fine:

Well, I can root the top level node in any one of the 5 distinct values, placing all values less that the root in the left subtree and all the values larger than the root in the right subtree. So the number of nodes in each subtree are:

Do you mean?

Left Subtree Right Sub Tree
0, 4 (0 as the root)
1, 3 (1 as the root)
2, 2 (2 as the root)
3, 1 (3 as the root)
4, 0 (4 as the root)
Also plz explain this term:
What do you mean by T(2)?
Tree with 2 as the root. How we get the following?
T(2) = T(1)*T(0) + T(0)*T(1)


Zulfi.

 

Do you mean?

Left Subtree Right Sub Tree
0, 4 (0 as the root)
1, 3 (1 as the root)
2, 2 (2 as the root)
3, 1 (3 as the root)
4, 0 (4 as the root)

No. Consider the following tree (and I REALLY wish you would start using a reasonable depiction of a tree).

|||3|||
||2||4||
|1||||5|
||||||

3 is the root of the tree. The left subtree consists of {1,2} and the right subtree consists of {3,4}.

Since the left subtree is independent of the right subtree, the total number of BSTs that I can make that have 3 as the root, is the product of how many BSTs I can make with the elements of the left subtree and how many I can make with the elements of the right.

What do you mean by T(2)?

Exactly what I stated: "T(N) is the number of BSTs that can be made with N distinct nodes"

I don't know how else to explain it.

T(3)=5 because with 3 distinct nodes we can make 5 distinct binary search trees?

What is unclear?

 

Hi,

3 is the root of the tree. The left subtree consists of {1,2} and the right subtree consists of {4,5}.

I understand this but i cant understand this:

0,4
1,3
2,2,
3,1
4,0

Which node is used as root above?
Sorry, I am taking lot of your time but i cant understand how you found T(3) for example? There are 5 bst's but there are only 3 terms in the equation:

T(3) = T(2)*T(0) + T(1)*T(1) + T(0)*T(2)

for which bst's are:

BST are :

1 (root)
2 (R)
3(R)
----------
2:

1(root)
3(R)
2(L)

----------


3:
3(root)
2(L)
1(L)
----------------------
4:
3(root)
1(L)
2(R)
---------------
5:
2 (root)
1(L) 3 (R)

Thanks for your time.
Zulfi.

 

Okay, I see what is tripping you up. I'll see if I can explain it a different way.

The function T(N) is the total number of BSTs that can be draw using a set of N distinct keys.

Given a set of N distinct keys, I can order and number them from smallest to largest as 1 through N.

The total number of BSTs that I can draw is the sum of the total number of BSTs that I can draw with 1 as the root, 2 as the root, 3 as the root, and so on all the way up to N as the root.

T(N) = (Number of BSTs with 1 as root)
+ (Number of BSTs with 2 as root)
+ (Number of BSTs with 3 as root)
+ ...
+ (Number of BSTs with k as root)
+ ...
+ (Number of BSTs with N as root)

So I have a sum of N terms. Let's look at a specific case and then generalize it.

I have N=10. How many BSTs can I draw that have 4 as the root?

Well, there are a total of N=10 nodes. With k=4 as the root, there will be 3 nodes that have to go in the left subtree and 6 nodes that have to go in the right subtree. Putting these in terms of N and k, there will be (k-1) nodes in the left subtree and (N-k) in the right tree. So with this knowledge, we can rewrite the above equation for T(N) as follows:

T(N) = (Number of BSTs with 0 nodes in the left substree and N-1 nodes in the right)
+ (Number of BSTs with 1 nodes in the left substree and N-2 nodes in the right)
+ (Number of BSTs with 2 nodes in the left substree and N-3 nodes in the right)
+ ...
+ (Number of BSTs with k-1 nodes in the left substree and N-k nodes in the right)
+ ...
+ (Number of BSTs with N-1 nodes in the left substree and 0 nodes in the right)

So now the question is, how many BSTs can I draw with k as the root knowing that there are (k-1) nodes in the left subtree and (N-k) nodes in the right subtree.

Looking at just the left subtree, if there are (k-1) nodes in that subtree, then there are T(k-1) possible BSTs. For each one of those, we can use one of the possible BSTs for the right subtree, which is T(N-k). So now we can write our expression for T(N) as

T(N) = T(0)*T(N-1)
+ T(1)*T(N-2)
+ T(2)*T(N-3)
+ ...
+ T(k-1)*T(N-k)
+ ...
+ T(N-1)*T(0)

This can be written very compactly as

\(
T(N)\:=\:\sum_{k=1}^{N} T(k-1)*T(N-k)
\)

 

Hi,
Thanks for teaching me all this. I would take some time.

Zulfi.

 

Hi,
Thanks again. I tried and I am able to understand this but for clear understanding i have to solve this whole thing on my own. I would try and if got problem i would let you know.

Zulfi.

 

Hi,
Thanks for teaching me all this. I would take some time.

Zulfi.

Hi,
Thanks again. I tried and I am able to understand this but for clear understanding i have to solve this whole thing on my own. I would try and if got problem i would let you know.

Zulfi.

Boy, you weren't kidding when you said you would take some time!

Good luck!