# Binary search trees from node

#### zulfi100

Joined Jun 7, 2012
656
Hi,
Kindly guide me with the following question:

How many dissimilar binary search trees can be made from three nodes which old the key values 1, 2 and 3?
Zulfi.

#### WBahn

Joined Mar 31, 2012
27,406
Zulfi! You KNOW that we want to see some effort on your part to work your own problems. Why won't you do that?

#### zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your response. Actually i dont know the formula. I have applied different arrangements and the answer is 1 but its not correct. I have considered 1 combinations with 2 as the root . I cant figure out any other possible arrangement because its not satisfying bst (binary search tree) property.

Kindly guide me.

Zulfi.

#### WBahn

Joined Mar 31, 2012
27,406

Draw all of the possible binary search trees that you can think of that have three unique nodes. Actually do it. Draw them and post them.

#### zulfi100

Joined Jun 7, 2012
656
Hi,

2
1 3
Following are not possible:
1
2 3 -------example 1
or
3
2 1 -------example2

Sorry for the formatting. First one is root and then left and right nodes.I am talking about formula because how the answer is 15. I dont think we have to 1st draw 15 bst to get this answer.
Kindly guide me.

Zulfi.

Last edited:

#### WBahn

Joined Mar 31, 2012
27,406
Why aren't the second two possible?

#### zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your continuous interest and time for my problem. Last 2 are not possible because they dont follow the binary search tree property.
Kindly guide me.

Zulfi.

#### WBahn

Joined Mar 31, 2012
27,406
What is the "binary search tree property" that you are referring to? State it and then describe why the last two don't follow it.

#### zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your interest in my question. Following link shows the binary search tree property:

http://cs.queensu.ca/~jstewart/applets/bst/bst-property.html

According to this property value of root node is greater than the value of all nodes in the left sub tree but its value should be less than the values of all nodes in the right subtree.

Kindly guide me with this problem.

zulfi.

#### WBahn

Joined Mar 31, 2012
27,406
Hi,
Thanks for your interest in my question. Following link shows the binary search tree property:

http://cs.queensu.ca/~jstewart/applets/bst/bst-property.html

According to this property value of root node is greater than the value of all nodes in the left sub tree but its value should be less than the values of all nodes in the right subtree.

Kindly guide me with this problem.

zulfi.
Okay, so pick one of the keys and place it as your root node. Then pick one of the other keys and identify every place where it could legally go. Draw a different tree for each possibility. Now add the third key, again identifying every place it can legally go and drawing a new tree for each one.

When you said that the answer was 15, where did that answer come from? How many different binary trees (as opposed to binary search trees) are there?

Your statement of the constraint on a binary search tree is close, but not quite correct. Think about what happens if you have mutliple keys with the same value.

#### zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your response. I did it and i found that there are several different bst possible. But in the exam, we wont have so much time to draw these trees so i have a feeling about a formula for this question. However i dont know any formula for this.

When you said that the answer was 15, where did that answer come from?
Its in the book.

How many different binary trees (as opposed to binary search trees) are there?
I found that there are 6 binary trees (2 as '1' as the root, 2 with 2 as a root, and 2 with 3 as a root).

Zulfi.

#### WBahn

Joined Mar 31, 2012
27,406
Quite being so cryptic. If you found six, then list them so that I can see what your thinkig is.

#### zulfi100

Joined Jun 7, 2012
656
Hi,
1
2 3

1
3 2

2
1 3 (bst)

2
3 1

3
2 1

3
1 2

Kindly guide about the correct answer. As you know question is related to bst.

Zulfi.

Last edited:

#### djsfantasi

Joined Apr 11, 2010
8,574
Have you double-checked your examples against the definition of a binary search tree?

#### WBahn

Joined Mar 31, 2012
27,406
@djsfantasi: In this case, I had asked him to draw all of the binary trees first, not the binary search trees.

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

or

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

#### zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your information. This would certainly increase the number of binary trees. I would write after some time.

Zulfi.

#### zulfi100

Joined Jun 7, 2012
656
Hi,
Thousands of thanks for providing me knowledge on this. Its great that we have people like you in this forum. Okay i would write the remaining trees
7: (bst)
1 (root)
2 (R)
3(R)
----------
8:
1(root)
3(R)
2(R)
--------
9:
1 (root)
2(L)
3(L)
----------------
10:
1(root)
3(L)
2(L)
----------------------
11:
1(root)
2(L)
3(R)
----------------
12:
1(root)
3(L)
2(R)
-------------
13:
1(root)
2(R)
3(L)
-----------------
14: (bst)
1(root)
3(R)
2(L)

=============
15:
2 (root)
1 (R)
3(R)
----------
16:
2(root)
3(R)
1(R)
--------
17:
2 (root)
1(L)
3(L)
----------------
18:
2(root)
3(L)
1(L)
----------------------
19: (bst)
2(root)
1(L)
3(R)
----------------
20:
2(root)
3(L)
1(R)
-------------
21:
2(root)
1(R)
3(L)
-----------------
22: (bst)
2(root)
3(R)
1(L)

=============
23:
3 (root)
1 (R)
2(R)
----------
24:
3(root)
2(R)
1(R)
--------
25:
3 (root)
1(L)
2(L)
----------------
26: (bst)
3(root)
2(L)
1(L)
----------------------
27: (bst)
3(root)
1(L)
2(R)
---------------
28:
3(root)
2(L)
1(R)
-------------
29:
3(root)
1(R)
2(L)
-----------------
30:
3(root)
2(R)
1(L)

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

the above are 24 trees. Previously i showed 6 trees (post #12). So total=30 trees.
Sorry i am not able to copy word tables on to the forum's client window.
Zulfi..

Last edited:

#### WBahn

Joined Mar 31, 2012
27,406
Well, you need to do something because they look identical and so there is no way I can tell what your tree structure is. Use the TABLE tag or attach a diagram.

I don't follow your logic. You say you have eight trees that can be replicated for keys 2 and 3. How does lead to 12 trees? And how does that then lead to 26 binary trees?

How can we tell you if your reasoning is correct when you don't give your reasoning?

Last edited:

#### djsfantasi

Joined Apr 11, 2010
8,574
@WBahn - missed that important distinction. Mea culpa.

#### WBahn

Joined Mar 31, 2012
27,406
@WBahn - missed that important distinction. Mea culpa.
Not to worry. Very easy to miss.