ALLInterview.com :: Home Page      
 Advertise your Business Here     
Browse  |   Placement Papers  |   Company  |   Code Snippets  |   Certifications  |   Visa Questions
Post Question  |   Post Answer  |   My Panel  |   Search  |   Articles  |   Topics  |   Errors
   Refer this Site  Refer This Site to Your Friends  Site Map  Contact Us      
   
 
Categories >> Software >> Operating Systems >> Data Structures
 


 

 
Question
How many different binary trees and binary search trees can
be made from three nodes that contain the key values 1, 2 & 3?
 Question Submitted By :: Data Structures
  I also faced this Question!!      
Answer Posted By  
 Answers were Sorted based on User's Feedback
Answer
# 1
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 ?    137 Yes 17 No
aisha
 
Answer
# 2
The Catalan Numbers should give an answer.. The answer is
C(3)= 5. 

Is This Answer Correct ?    47 Yes 18 No
gautham
 
 
Answer
# 3
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 ?    69 Yes 45 No
poornakala
 
Answer
# 4
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 33 No
sreekumar
 
Answer
# 5
(2n C n) / (n+1) is the Number of BST if N is the number of
integer/value; 

Is This Answer Correct ?    14 Yes 7 No
shekhar
 
Answer
# 6
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 7 No
vinoth kumar.r
 
Answer
# 7
1oth answer is xactly correst ie,BST=5 & BT=30 

Is This Answer Correct ?    5 Yes 0 No
baljinder
 
Answer
# 8
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 ?    6 Yes 5 No
babugct
 
Answer
# 9
number of binary search tree= (2n)!/{n!*(n+1)!}
and number of binary tree=(2n)!/(n+1)! 

Is This Answer Correct ?    1 Yes 0 No
vipul
 
Answer
# 10
Formula For BST is
{(2n)!/(n!*n)}/(n+1)
So for
N=1 BST=1
N=2 BST=2
N=3 BST=5
N=4 BST=14
N=5 BST=42
and so on 

Is This Answer Correct ?    1 Yes 0 No
hazrat hussain
 

 
 
 
Other Data Structures Interview Questions
 
  Question Asked @ Answers
 
Convert following infix expression to the prefix expression. a - b + c * (d / e - (f + g)) microsoft 30
how to search an element in sorted linked list with time complexity is O(log n). wipro 3
How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that cycle? citrix 12
Let the G be a graph with 100 vertices numbered 1 to 100 Two vertices i and j are adjecnt if | i-j| =8 or | i-j| =12. The Number of connected components in G is ?   4
Tell me real world example of polymorphism and encapsulation . cybage 7
difference between the run time polymorphism and compile time poly morphism and about virtual function. cybage 2
Which sort show the best average behavior?   9
create an singly linked lists and reverse the lists by interchanging the links and not the data? microsoft 13
what is AVL tree? ads 5
What is B+ tree? bmc 6
how a polynomial such as 6x^6+4x^3-2x+10 can be represnted by linked list?write an algorithm that reads such an polynomial   1
Write a Binary Search program microsoft 7
 
For more Data Structures Interview Questions Click Here