6 votes 6 votes What is the number of binary trees with 4 nodes which when traversed in pre-order gives the sequence 1,2,3,4? DS data-structures binary-tree + – srestha asked Mar 22, 2018 srestha 717 views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply joshi_nitish commented Mar 22, 2018 reply Follow Share it is equal to no. of binary tree structures possible i.e nth catalan number 4th catalan no. = 14 7 votes 7 votes akshat sharma commented Mar 22, 2018 reply Follow Share https://www.geeksforgeeks.org/number-of-binary-trees-for-given-preorder-sequence-length/ it might help 3 votes 3 votes Mk Utkarsh commented Mar 22, 2018 reply Follow Share It's same as binary trees possible with n unlabeled nodes https://gateoverflow.in/202554/binary-search-tree 5 votes 5 votes srestha commented Mar 22, 2018 reply Follow Share here preorder traversal and leveling of node 1,2,3,4 both should satisfy So, here we can say 1 should be in root if 1 is root 2,3,4 all greater than 1 So, cannot be in it's left subtree Then how catalan number could give the answer? catalan number only satisfy unleveled node,rt? Is sequence and leveling of node same? 2 votes 2 votes Tesla! commented Mar 22, 2018 reply Follow Share Because it's binary tree not binary search tree :) 2 votes 2 votes srestha commented Mar 22, 2018 reply Follow Share yes thanks all 1 votes 1 votes rish1602 commented Jul 23, 2021 reply Follow Share @srestha @ Mk Utkarsh I think the answer be 6 since the question has mentioned about the preorder traversal ? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes $(2n)!/(n+1)!*n!$ where n= no. of nodes In this case $(8)!/(4+1)!*4!$ = 14 Arjun Satpathy answered Apr 13, 2018 Arjun Satpathy comment Share Follow See all 0 reply Please log in or register to add a comment.