Binary search trees from node

WBahn

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

Thread Starter

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
29,977
Who's talking about a formula?

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.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your reply. Only one bst possible:

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:

Thread Starter

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
29,977
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.
 

WBahn

Joined Mar 31, 2012
29,977
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.
 

Thread Starter

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).

Kindly let me know about your response about my answer.
Zulfi.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your reply. I was avoiding drawing. 6 trees are:
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:

WBahn

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

@zulfi: What about
|1|||
||2||
|3|||

or

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

Thread Starter

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.
 

Thread Starter

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.
Kindly guide me about my answer plz.
Sorry i am not able to copy word tables on to the forum's client window.
Zulfi..
 
Last edited:

WBahn

Joined Mar 31, 2012
29,977
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:
Top