34 34 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. Data Structures gate1995 data-structures binary-tree normal descriptive + – Kathleen 6.8k views answer comment Share Follow Print See all 2 Comments 2 2 Comments reply smsubham commented Dec 21, 2017 reply Follow flag 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. 6 6 replyShare Kiyoshi commented Aug 31, 2021 reply Follow flag Similar question.. https://gateoverflow.in/859/gate-cse-2002-question-6 2 2 replyShare Please log in or register to add a comment.
Best answer 42 42 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 2 2 Comments reply Abhrajyoti00 commented Nov 5, 2022 reply Follow flag 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$ 10 10 replyShare Digvi_sp commented Oct 15, 2023 reply Follow flag 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 0 replyShare Please log in or register to add a comment.
42 42 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 0 reply Please log in or register to add a comment.
1 1 vote Ans is 5 (catalian no.) rishu_darkshadow answered Oct 7, 2017 rishu_darkshadow comment Share Follow 0 reply Please log in or register to add a comment.
1 1 vote Only 5 Binary Trees possible where Post-order sequence is A, B, C amaanshaikh_27 answered Apr 24 amaanshaikh_27 comment Share Follow 0 reply Please log in or register to add a comment.
