How many different binary trees and binary search trees can
be made from three nodes that contain the key values 1, 2 & 3?
Answers were Sorted based on User's Feedback
Answer / aisha
Binary tree :- 30 as follows
1 1 2 2 3 3
/ \ / \ / \ / \ / \ / \
2 3 3 2 1 3 3 1 1 2 2 1
1 1 1 1 1 1 1 1
/ / / / \ \ \ \
2 3 2 3 2 3 2 3
/ / \ \ / / \ \
3 2 3 2 3 2 3 2
2 2 2 2 2 2 2 2
/ / / / \ \ \ \
1 3 1 3 1 3 1 3
/ / \ \ / / \ \
3 1 3 1 3 1 3 1
3 3 3 3 3 3 3 3
/ / / / \ \ \ \
2 1 2 1 2 1 2 1
/ / \ \ / / \ \
1 2 1 2 1 2 1 2
Binary search tree :-5 as follows
1 1 2 3 3
\ \ / \ / /
2 3 1 3 1 2
\ / \ /
3 2 2 1
Is This Answer Correct ? | 148 Yes | 22 No |
Answer / gautham
The Catalan Numbers should give an answer.. The answer is
C(3)= 5.
Is This Answer Correct ? | 47 Yes | 21 No |
Answer / poornakala
for binary search tree, no of trees, (2^n)-n... here 8-3=5
trees... u can draw n see...
for binary tree, no of trees n(2^n)-n here 3*5=15...
replace node in each bst with other two values and see....
Is This Answer Correct ? | 72 Yes | 48 No |
Answer / sreekumar
Nubmerof Nodes| BT Possible | BST Possible|
==============+================+==============
1 | 1 | 1
--------------+----------------+---------------
2 | 2 | 2
--------------+----------------+---------------
3 | 6 | 5
--------------+----------------+---------------
4 | 24 | 14
--------------+----------------+--------------
. | . | .
--------------+----------------+--------------
| |
| | 2n 1
| | C * ------
n | n! | n (n+1)
------------------------------------------------------
C=Combinations
n!,2nCn /(n+1)
Is This Answer Correct ? | 57 Yes | 35 No |
Answer / shekhar
(2n C n) / (n+1) is the Number of BST if N is the number of
integer/value;
Is This Answer Correct ? | 17 Yes | 8 No |
Binary search trees care only about the inorder traversal of
the tree. And specifying inorder traversal of a tree doesnt
mean there is a unique representation of it.
5 Binary search trees are possible
Is This Answer Correct ? | 13 Yes | 9 No |
Answer / baljinder
1oth answer is xactly correst ie,BST=5 & BT=30
Is This Answer Correct ? | 5 Yes | 1 No |
Answer / vipul
number of binary search tree= (2n)!/{n!*(n+1)!}
and number of binary tree=(2n)!/(n+1)!
Is This Answer Correct ? | 3 Yes | 0 No |
Answer / shweta
for binary tree ans is 5, the general formula is (2^n)-n
for binary search tree no. of tree possible is 3.
as root data can be either 1, 2 or 3
Is This Answer Correct ? | 39 Yes | 38 No |
Answer / babugct
All the above answers are wrong............
please post some correct answer...
as far as my concern,,,
no.of binary trees=n!*(2^(n)-n)
no.of bst's=2^(n)-n...
pls inform if wrong
Is This Answer Correct ? | 7 Yes | 6 No |
What are different types of linked lists?
what is R-B tree
Write programs for Bubble Sort, Quick sort
What type of algorithm is binary search?
How would you dynamically allocate a one-dimensional and two-dimensional array of integers?
How will you explain circular linked list?
What is a b+ tree? Explain its uses.
What is heap tree?
What are the parts of a linked list?
Define a complete binary tree?
How does quicksort partition work?
What is a data structure?