# Binary search trees from node

Discussion in 'Homework Help' started by zulfi100, Jul 1, 2013.

1. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
Hi,
Kindly guide me with the following question:

Zulfi.

2. ### WBahn Moderator

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

3. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
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.

4. ### WBahn Moderator

Mar 31, 2012
17,715
4,786

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.

5. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
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: Jul 13, 2013
6. ### WBahn Moderator

Mar 31, 2012
17,715
4,786
Why aren't the second two possible?

7. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
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.

8. ### WBahn Moderator

Mar 31, 2012
17,715
4,786
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.

9. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
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.

10. ### WBahn Moderator

Mar 31, 2012
17,715
4,786
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.

11. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
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.

Its in the book.

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.

12. ### WBahn Moderator

Mar 31, 2012
17,715
4,786
Quite being so cryptic. If you found six, then list them so that I can see what your thinkig is.

13. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
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: Jul 18, 2013
14. ### djsfantasi AAC Fanatic!

Apr 11, 2010
2,786
825
Have you double-checked your examples against the definition of a binary search tree?

15. ### WBahn Moderator

Mar 31, 2012
17,715
4,786
@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

16. ### zulfi100 Thread Starter Member

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

Zulfi.

17. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
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: Jul 18, 2013
18. ### WBahn Moderator

Mar 31, 2012
17,715
4,786
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: Jul 17, 2013
19. ### djsfantasi AAC Fanatic!

Apr 11, 2010
2,786
825
@WBahn - missed that important distinction. Mea culpa.

20. ### WBahn Moderator

Mar 31, 2012
17,715
4,786
Not to worry. Very easy to miss.