Latest DATA STRUCTURE Aptitude Question SOLUTION: How many different binary trees and binary search trees can be made from three nodes that contain the key values 1, 2 & 3?

• Placement Papers
• /
• DATA STRUCTURE
• /
• Programming
• /
• Technical

DATA STRUCTURE Question Papers:

(#M40019022) DATA STRUCTURE Programming question DATA STRUCTURE QUESTIONS Keep an EYE

How many different binary trees and binary search trees
can be made from three nodes that contain the key values
1, 2 & 3?

Asked In DATA STRUCTURE (11 years ago)

Unsolved Read Solution (5)

Is this Puzzle helpful?   (12)   (7) Submit Your Solution Technical

Read Solution (5) :

abhishek verma  (10 years ago)

BST = 2n!/n!(n+1)!
BT = 2n!(n+1)!
given n = 3
so,BST = 6!/3!4! = 5;
and,BT = 6!/4! = 30;

Is this solution Helpfull? Yes (6) | No   

Rahul Bhadana  (11 years ago)

1) in Binary Search Tree(BST) their is a order in which every node has left child which is smaller than it and right child which is larger than it. and in case of binary Tree such order is not needed.

YES by using key values 1 , 2 & 3 we can make 5 different BST while using exactly the same key values as node we can make 30 different Binary Tree(as their is no order while arranging the nodes).

Is this solution Helpfull? Yes (2) | No   

SURAJIT DAS  (10 years ago)

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 solution Helpfull? Yes (1) | No (2)  

jitendra kumar  (11 years ago)

i think,binary tree 12 and binary search tree 4

Is this solution Helpfull? Yes | No (2)  

SUSMITHA  (6 years ago)

countBST(n) = (2n)!/(n+1)!*n!
countBT = countBST(n) * n!

Is this solution Helpfull? Yes | No   

Please Login to Read Solution.