Binary Search Tree

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
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?

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
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.
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
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'.$