20 votes 20 votes Draw all binary trees having exactly three nodes labeled $A, B$ and $C$ on which preorder traversal gives the sequence $C, B, A$. DS gatecse-2002 data-structures binary-tree easy descriptive + – Kathleen asked Sep 15, 2014 • edited Dec 25, 2017 by kenzou Kathleen 2.6k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Kiyoshi commented Aug 31, 2021 reply Follow Share Similar question asked before.. https://gateoverflow.in/2667/gate-cse-1995-question-6 0 votes 0 votes vivek18 commented Jan 6, 2023 reply Follow Share number of different unlabelled binary tree of n node = catalan no.(n) we can put a,b,c in each binary tree one way to produce given preorder sequence so answer is catalan number 1 votes 1 votes Please log in or register to add a comment.
Best answer 25 votes 25 votes $5$ Binary trees. Anu answered May 30, 2015 • edited Jul 3, 2019 by Lakshman Bhaiya Anu comment Share Follow See all 2 Comments See all 2 2 Comments reply Puja Mishra commented Dec 24, 2017 reply Follow Share ...... 0 votes 0 votes KUSHAGRA गुप्ता commented Dec 29, 2019 reply Follow Share $\#$ of preorder tree $=\#$ of unlabelled trees$=$ catalan $\#=\dfrac{^{2n}C_{n}}{n+1}=\dfrac{^6C_{3}}{4}=5$ 8 votes 8 votes Please log in or register to add a comment.