The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
168 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 ?
in Programming by (475 points)
edited by | 168 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.

by Boss (34.6k points)
selected by

Related questions

+1 vote
1 answer
3
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
50,092 questions
55,239 answers
190,758 comments
85,996 users