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 data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?
Write program for Quick sort ?
Explain Array of pointers?
Which is the slowest sorting algorithm?
How would you reverse characters of an array without using indexing in the array.
Can arraylist be null?
What is ascending and descending order?
Define hash function?
What is a data structure definition?
What are the major data structures used in the network data model?
What does stack top do?
State the advantages of using postfix notations?