3 votes 3 votes How many numbers of binary tree can be created with 4 nodes which when traversed in post order gives the sequence D, C, B, A? 1. 14 2. 15 3. 10 4. 16 Please Explain. Is there any formula? DS data-structures binary-tree + – nishant279 asked Sep 16, 2017 nishant279 3.7k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 4 votes 4 votes Here one thing to note : No of trees with given preorder traversal = No of trees with given postorder traversal = No of trees with given inorder traversal = No of BSTs = No of unlabelled binary trees = Catalan Number [ C(2n,n) / (n+1) ] Here n = 4 So substituting n = 4 in the expression we get : Number of binary trees with given postorder traversal = C(8,4) / 5 = [ 8 * 7 * 6 * 5 ] / [ 1 * 2 * 3 * 4 * 5 ] = 14 Habibkhan answered Sep 16, 2017 • selected Sep 18, 2017 by Habibkhan Habibkhan comment Share Follow See all 3 Comments See all 3 3 Comments reply rishu_darkshadow commented Sep 18, 2017 reply Follow Share sir, it means number of labeled binary tree with n nodes and having same inorder/preorder/postorder traversal= catelan no. AND number of labeled binary tree with n nodes= catalan no. * n! plzz clearify me 2 votes 2 votes Habibkhan commented Sep 18, 2017 reply Follow Share Yes u r right..:) 0 votes 0 votes rishu_darkshadow commented Sep 18, 2017 reply Follow Share thank you sir for your helpful response :) 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes No. Of trees with given postorder= no.of trees with unlabeled nodes =C(2n,n)/n+1 For n=4 No.of trees possible=C(8,4)/5 =14 Priyanka Agarwal answered Oct 4, 2017 Priyanka Agarwal comment Share Follow See all 0 reply Please log in or register to add a comment.