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
    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.
     
  5. zulfi100

    Thread Starter Member

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

    Kindly let me know about your response about my answer.
    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,
    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: 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.

    @zulfi: What about
    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.
    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: 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.
     
Loading...