search
Log In
1 vote
196 views
1) How many ways we can traverse 1,2,3,4 in BST?

2) How many ways we can insert 1,2,3,4 in BST?

______________________________________________________________________

How both are different in calculation of BST?Why they are use different formula?
in DS 196 views
0
How many ways we can traverse 1,2,3,4 in BST?

traverse means pre-order? or post order? otherwise in-order
0
any order
0
No.of BST's possible with n nodes = $\frac{C(2n,n)}{n+1}$ ===> consider these are structures

while inserting, any order leads to a BST ==> no.of orders = n!

let take pre-order:-

Every structure has different pre-order===> no.of different pre order = no.of structures

 

( some of the orders can not possible in pre-order

ex:- let take three nodes ==>1,2,3

total insertions orders = 3!=6

total pre-orders = no.of structures = 5

231 which can't possible as pre-order )
0
r u inserting or traversing?
0
inserting:- n!

traversing:- $\frac{C(2n,n)}{n+1}$
0
isnot inserting $\binom{n}{r}$

and traversing $2^{3}+2^{2}\times 2 ??$
0
elaborate it more...
0
the no.of inserting ways, already we disccused right?
0
See inserting or traversing in BST means either insertion in left subtree or insertion in right subtree ,i.e. $2^{x}$

but $n!$ means insertion in a rowwise(like 6 child sitting in a row kind of)

right?
0

First fix the traversal,

Traversing means already BST formed ===> no.of BST patterns = no.of different traversals

 

 

 inserting in BST means either insertion in left sub tree or insertion in right sub tree ,i.e. 2x

it is wrong.... just blindly follow the procedure on the paper.

 let take at height=0 (root) ---- 1 choice ---- 1st insertion

2nd new insertion ---> inserting can go either left or right ---- 2  ( just stick the node to left for further analysis )

3 rd new insertion --->

                      at height=1, we can insert at right side

                       at height=2, we can insert at right or left

               ∴ Therefore 3 choices.... ( just stick the node to right at height=2 for further analysis )

4th new insertion --->

                      at height=1, we can insert at right side

                       at height=2, we can insert at left side

                       at height=3, we can insert at right or left

               ∴ Therefore 4 choices.... ( just stick the node to left at height=2 for further analysis )

we can conclude that, at nth insertion, there are n choices

Total = 1.2.3.4....n = n!

 

if you didn't get this, 

with 4 nodes ===> 4! permutations formed and note down all

each permutation should be lead to a BST, may it duplicate... you are not interested into no.BST therefore duplicates doesn't matter to you

0
<p>Shouldn't &nbsp;for inserting equals to no of different bst structures that can be formed $\frac{\binom{2n}{n}}{n+1}$ this would be equal to traversing na since every structure&nbsp; would have different traversal sequence&nbsp;</p>
0

@Kaluti, i didn't get your comment

0
I mean formula used for calculation of no of bst should be same for calculation of no of traversal
0
did you comment for me or srestha mam ?

if it is for me, in my comments also i said that only, refer my comments

if it is for srestha mam, leave it
0

@Kaluti

no of bst should be same for calculation of no of traversal

what is meaning of it? 

1 Answer

0 votes
I didn't understand, for inserting we can insert in 1/(n+1)*2nCn ways and for traversing these it will be the same right? @Masthan ?Please correct me if I'm wrong.

Related questions

1 vote
1 answer
1
183 views
AVL tree is created by inserting the keys 2, 6, 1, 5, 3, 4, 7 in the given order (Assume the tree is initially empty). Then the level order traversals of the tree would be. 2, 1, 3, 5, 4, 6, 7 3, 2, 5, 1, 6, 4, 7 2, 1, 3, 4, 5 ... even after knowing all the concepts. After 2 or 3 rotations I get stuck trying to figure out which way to rotate. Please help me with the proper steps in this question.
asked Jan 6, 2019 in DS Gupta731 183 views
0 votes
1 answer
2
84 views
Consider the following routine bool do(struct node *root) { if(!root) return true; else if(( root ---> left != NULL && root ---> data < root ---> left---> data) ||(root-->right != NULL && root ---> data > root ----> right ----> data)) return false; else return (do( ... do(root---> right)); } What does they do() check whether a given tree is: $A)$ Max heap $B)$ Min Heap $C)$BST $D)$ Binary Tree
asked Nov 6, 2018 in DS Lakshman Patel RJIT 84 views
0 votes
0 answers
3
120 views
Consider a binary search tree for the following sequence of nodes $a,b,g,f,c,e,d$ What is the resultant tree if splaying is done at $'d'.$
asked Oct 28, 2018 in DS Lakshman Patel RJIT 120 views
2 votes
1 answer
4
308 views
Number of ways we can insert 5,6,9,10 in the nodes of BST, such that height of BST is either 2 or 3?
asked Aug 17, 2018 in DS srestha 308 views
...