data structure

Question

Comments

pls someone explain this

---

first find both arrays and then apply longest common subsequence algorithm of dynamic programming

---

first find both arrays and then apply longest common subsequence algorithm of dynamic programming

This will take forever. 

Answer 1

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.

Comments

In Preorder sequence, You have made little mistake (93,92....not 92,93)..Hence, the answer would be $6$.

Answer 2

Theorem : Order of the leaf (leaves) of a binary tree in the tree traversals(Pre,Post,In-order) :  In all the three traversals the order of the leaves are always the same. (Hint : All These Traversals: Preorder, Inorder and Postorder Traversals are Depth-First Traversals. In All of them, Left Node is processed before Right Node (only the Root oscillates))

Result (derivable from above theorem) : The length of the longest common subsequence(LCS) between Pre-order and Post-order sequences of a binary tree will be exactly equal to the Number of Leaves in the Binary Tree. (Can be proved using the above theorem and by using Proof by contradiction technique ...Hint : Let a intermediate node be present in the LCS and then show that either the length of LCS will decrease or will remain same)

Hence, Just count the number of leaves in the given BST and you have your answer. Answer will be $6$ (as there will be $6$ leaves in the BST given)

Answer 3

LCS OF left =3

and right =3

 A+B= 6

the sequence (88 65 52 77 92 93) is worng

correct sequence= (88 65 52 77 93 92)