traverse means pre-order? or post order? otherwise in-order

The Gateway to Computer Science Excellence

+1 vote

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?

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?

0

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

traverse means pre-order? or post order? otherwise in-order

traverse means pre-order? or post order? otherwise in-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 )

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

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?

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. 2

^{x}

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

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

2^{nd} 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 )

4^{th} 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 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 would have different traversal sequence </p>

0

52,217 questions

59,907 answers

201,099 comments

118,145 users