Register

Ds-tree

318 views
0 votes
0 votes
Given numbers from 1 to 8. Number 5 is the root of BST.How many number of BST are possible with given constraint.
User Avatar

2 Answers

1 votes
1 votes
70 use diagram or C(4)+C(3)=14*5=70 use and rule not sum rule ,where C(n) catalan no.
• edited by
User Avatar
1 votes
1 votes

since 5 is the root

then
4 elements in left(1234)  and  3 elements in right(678)

Left side possibilities: 

 Cn = 2nCn / n+1

⟹C4=8C4 / 5=14.

Right side possibilities:

C3=6C3 / 4 = 5.

Total possibilities=14×5=70.

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
saurav raghaw asked Dec 26, 2018
484 views
TREE DS
The number of nodes of degree one in a complete binary tree of 2$^{30}$ nodes is? (1) 2$^{29}$ +1 (2) 2$^{29}$ (3) 2$^{30}$ (4) 1
The number of nodes of degree one in a complete binary tree of 2$^{30}$ nodes is?(1) 2$^{29}$ +1(2) 2$^{29}$(3) 2$^{30}$(4) 1
User Avatar
1 votes
1 votes
0 answers
2
garg div asked Sep 14, 2017
695 views
DS - weighted balanced tree
A weight balanced tree is a binary tree in which for each node, the no. of nodes in the left sub tree is atleast half and at most twice the no. of nodes in the right sub tree. The maximum possible height of such a tree with n nodes is best described by? Please explain me how to write recurrence relation for such questions
A weight balanced tree is a binary tree in which for each node, the no. of nodes in the left sub tree is atleast half and at most twice the no. of nodes in the right sub ...
User Avatar
1 votes
1 votes
2 answers
3
mystylecse asked Aug 6, 2017
864 views
Binary Tree DS
How many distinct binary tree can be formed with three distinct keys? Please help me to find the correct answer?
How many distinct binary tree can be formed with three distinct keys?Please help me to find the correct answer?
User Avatar
Link Copied!