Register

GATE CSE 1995 | Question: 6

• recategorized by
3,705 views
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.
• recategorized by
User Avatar

3 Answers

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. 

  1. One with $C$ as root and left child as $A$ and right child $B$.
  2. Second with $C$ as root, $B$ as left child and $A$ as again left child of $B$.
  3. Third with $C$ as root, $B$ as left child and $A$ as right child of $B$.
  4. Fourth with $C$ as root, $B$ as right child and $A$ as right child of $B$.
  5. Fifth with $C$ as root, $B$ as right child and $A$ as left child of $B$.
• edited by
User Avatar
31 votes
31 votes

T

Whenever only one order is asked for a tree, total no. of trees = total no. of structures possible.

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

43 votes
43 votes
6 answers
1
Kathleen asked Oct 8, 2014
36,051 views
GATE CSE 1995 | Question: 1.17
A binary tree $T$ has $n$ leaf nodes. The number of nodes of degree $2$ in $T$ is $\log_2 n$ $n-1$ $n$ $2^n$
A binary tree $T$ has $n$ leaf nodes. The number of nodes of degree $2$ in $T$ is$\log_2 n$$n-1$$n$$2^n$
User Avatar
7 votes
7 votes
1 answer
2
go_editor asked Feb 12, 2018
2,566 views
GATE CSE 1995 | Question: 15-b
What is the equivalent minimal Boolean expression (in sum of products form) for the Karnaugh map given below?
What is the equivalent minimal Boolean expression (in sum of products form) for the Karnaugh map given below?
User Avatar
24 votes
24 votes
3 answers
3
Kathleen asked Oct 8, 2014
4,487 views
GATE CSE 1995 | Question: 27
Consider the relation scheme. ... for the publisher with PNAME='TECHNICAL PUBLISHERS'. Get the names of all authors who have published a book for any publisher located in Madras
Consider the relation scheme.$$\begin{array}{ll} \text{AUTHOR} & \text{(ANAME, INSTITUTION, ACITY, AGE)} \\\hline \text{PUBLISHER} & \text{(PNAME, PCITY)} \\\hline \te...
User Avatar
28 votes
28 votes
6 answers
4
Kathleen asked Oct 8, 2014
11,268 views
GATE CSE 1995 | Question: 26
Consider the relation scheme $R(A, B, C)$ with the following functional dependencies: $A, B \rightarrow C,$ $C \rightarrow A$ Show that the scheme $R$ is in $3\text{NF}$ but not in $\text{BCNF}$. Determine the minimal keys of relation $R$.
Consider the relation scheme $R(A, B, C)$ with the following functional dependencies:$A, B \rightarrow C,$$C \rightarrow A$Show that the scheme $R$ is in $3\text{NF}$ but...
User Avatar
Link Copied!