If we try to approach this problem in a straight forward manner i.e. constructing a 15x15 matrix to find the length of LCS using dynamic programming, it might be a bit hassle-prone and time consuming.
Instead, we can observe the properties of the traversals and try to make the problem a bit short.
preorder traversal of a BST=(Root)(Left)(Right)
postorder traversal of a BST=(Left)(Right)(Root)
things to observe:
1. In any of the possible Longest common subsequences Root can never be part, as the Root is at the extreme ends in both the traversals, and in this particular problem every element is distinct, so the longest common subsequence will be limited to the (Left)(Right) part of both the traversals.
(Root)(Left)(Right)
(Left)(Right)(Root)
2. Moreover, in both of the traversals (Left) and (Right) contains the same elements, as they constitute the left subtree and the right subtree of the tree. The longest common subsequence=Longest common subsequence of the (Left) part of both the traversals+Longest common subsequence of the (Right) part of both the traversals.
Preorder: 50 27 16 4 12 34 29 44 88 65 52 77 92 93
=>(Root) (Left) (Right)=>(50) (27 16 4 12 34 29 44) (88 65 52 77 92 93)
Postorder:12 4 16 29 44 34 27 52 77 65 92 93 88 50
=>(Left) (Right) (Root)=>(12 4 16 29 44 34 27) (52 77 65 92 93 88) (50)
Now all we have to do is compute LCS of (Left) between both the traversals and LCS of (Right) between both the traversals. And the answer will be simply the summation of them.
Here the we can work with 8x8 matrix(in case of (Left)) and 7x7 matrix(in case of (Right)) and apply Dynamic Programming to it, which, as we can see minimizes the working size of the matrix considerably(Though we have to compute it two times, one for (Left) and one for (Right)), or we can in this particular case even manually count it.
Either way, The Size of the Longest Common Subsequence for the (Left) part = 3
The Size of the Longest Common Subsequence for the (Right) part = 4
So, finally, the Total size of the longest common subsequence=4+3=7
Correct me if I am wrong.