25 votes 25 votes What is the number of binary trees with $3$ nodes which when traversed in post-order give the sequence $A, B, C ?$ Draw all these binary trees. DS gate1995 data-structures binary-tree normal descriptive + – Kathleen asked Oct 8, 2014 • recategorized Apr 25, 2021 by Lakshman Bhaiya Kathleen 3.7k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply smsubham commented Dec 21, 2017 reply Follow Share Approach Draw all the unlabelled Binary Tree possible with 3 nodes. i,e, 5 Traverse postorder in each of them to a fill letters so that we get A B C from post-order traversal. 3 votes 3 votes Kiyoshi commented Aug 31, 2021 reply Follow Share Similar question.. https://gateoverflow.in/859/gate-cse-2002-question-6 2 votes 2 votes Please log in or register to add a comment.
Best answer 34 votes 34 votes There are only five such binary trees. This is given by $3^{\text{rd}}$ Catalan number as here we are finding the number of structurally similar binary trees with $3$ nodes. One with $C$ as root and left child as $A$ and right child $B$. Second with $C$ as root, $B$ as left child and $A$ as again left child of $B$. Third with $C$ as root, $B$ as left child and $A$ as right child of $B$. Fourth with $C$ as root, $B$ as right child and $A$ as right child of $B$. Fifth with $C$ as root, $B$ as right child and $A$ as left child of $B$. Gate Keeda answered Oct 8, 2014 • edited Apr 25, 2021 by Lakshman Bhaiya Gate Keeda comment Share Follow See all 2 Comments See all 2 2 Comments reply Abhrajyoti00 commented Nov 5, 2022 reply Follow Share With $n^{th}$ Catalan no. ($C_n$) we get the no of distinct structures for $n$ unlabeled nodes. Now for a particular post order of a particular structure, there can be only $1$ such tree.. Hence the answer for this question is $C_n$ 4 votes 4 votes Digvi_sp commented Oct 15, 2023 reply Follow Share can you explain how we are finding structurally similar binary trees here? the 5 trees you have mentioned do not seem to be structurally similar. 0 votes 0 votes Please log in or register to add a comment.
31 votes 31 votes T Whenever only one order is asked for a tree, total no. of trees = total no. of structures possible. ravi_ssj4 answered Aug 20, 2016 ravi_ssj4 comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Ans is 5 (catalian no.) rishu_darkshadow answered Oct 7, 2017 rishu_darkshadow comment Share Follow See all 0 reply Please log in or register to add a comment.