The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
153 views
assume the preorder tŕaversal of binary tree is "abc" how many total different binary trees are possible whose postorder traversal.is "cba" with the given preorder traversal.??

how to find it ?
asked in Programming by (475 points)
edited by | 153 views
+1

From preoder condition you can sort the number of trees using 2nCn/(n+1) n

Total trees = [2nCn/(n+1)]*n! = 30  (n = number of distinct labeled nodes.)

To sort them from preorder condition use = [2nCn/(n+1)] = 5 trees which matches the given preorder conditions.

Now draw them and sort according to postorder. (out of 5 you will get 4 with matching given conditions)

        A

    B

C

A

   B

       C

      A

 B

   C

 A

       B

   C

i haven't found any other way except this.

1 Answer

+1 vote
Best answer

4 is right.

answered by Boss (33.9k points)
selected by

Related questions

+1 vote
1 answer
3
0 votes
3 answers
7
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,588 questions
54,197 answers
187,535 comments
71,152 users