1 votes 1 votes 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? DS data-structures binary-search-tree + – srestha asked Aug 18, 2018 srestha 1.0k views answer comment Share Follow See all 15 Comments See all 15 15 Comments reply Shaik Masthan commented Aug 18, 2018 reply Follow Share How many ways we can traverse 1,2,3,4 in BST? traverse means pre-order? or post order? otherwise in-order 0 votes 0 votes srestha commented Aug 18, 2018 reply Follow Share any order 0 votes 0 votes Shaik Masthan commented Aug 18, 2018 reply Follow Share 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 votes 0 votes srestha commented Aug 18, 2018 reply Follow Share r u inserting or traversing? 0 votes 0 votes Shaik Masthan commented Aug 18, 2018 reply Follow Share inserting:- n! traversing:- $\frac{C(2n,n)}{n+1}$ 0 votes 0 votes srestha commented Aug 18, 2018 reply Follow Share isnot inserting $\binom{n}{r}$ and traversing $2^{3}+2^{2}\times 2 ??$ 0 votes 0 votes Shaik Masthan commented Aug 18, 2018 reply Follow Share elaborate it more... 0 votes 0 votes Shaik Masthan commented Aug 18, 2018 reply Follow Share the no.of inserting ways, already we disccused right? 0 votes 0 votes srestha commented Aug 18, 2018 reply Follow Share 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 votes 0 votes Shaik Masthan commented Aug 19, 2018 reply Follow Share 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 votes 0 votes Kaluti commented Aug 22, 2018 i edited by Kaluti Aug 22, 2018 reply Follow Share <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 votes 0 votes Shaik Masthan commented Aug 22, 2018 reply Follow Share @Kaluti, i didn't get your comment 0 votes 0 votes Kaluti commented Aug 22, 2018 reply Follow Share I mean formula used for calculation of no of bst should be same for calculation of no of traversal 0 votes 0 votes Shaik Masthan commented Aug 22, 2018 reply Follow Share 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 votes 0 votes srestha commented Aug 22, 2018 reply Follow Share @Kaluti no of bst should be same for calculation of no of traversal what is meaning of it? 0 votes 0 votes Please log in or register to add a comment.
0 votes 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. Iqra Islam answered Sep 5, 2018 Iqra Islam comment Share Follow See all 0 reply Please log in or register to add a comment.