3,482 views
1 votes
1 votes

A binary search tree was constructed by inserting following elements into an initially empty binary tree.
                                                   50, 27, 16, 88, 34, 65, 52, 77, 93, 4, 12, 29, 44, 92
Preorder and postorder traversals of the resultant binary search tree were stored in arrays A and B respectively. The length of LCS present in these to array A and B ___________.

Everything is ok here,, But not getting how length of LCS is calculated here.

2 Answers

Best answer
1 votes
1 votes
Preorder : 50 27 16 4 12 34 29 44 88 65 52 77 93 92

Postorder : 12 4 16 29 44 34 27 52 77 65 52 93 88 50

 

The LCS will be 16 29 44 52 77 93
selected by
1 votes
1 votes
preorder : 50,27,16,4,12,34,29,44,88,65,52,77,93,92

postorder :12,4,16,29,44,34,27,52,77,65,92,93,88,50

now, we apply algorithm to 14 * 14 table (fill them using longest commomn subsequence algorithm)

then we find longest common subsequence is 12,29,44,52,77,92

Related questions

0 votes
0 votes
1 answer
1
1 votes
1 votes
1 answer
2
pradeepchaudhary asked Aug 19, 2018
19,111 views
8. What are the worst case and average case complexities of a binary search tree?a) O(n), O(n)b) O(logn), O(logn)c) O(logn), O(n)d) O(n), O(logn)
5 votes
5 votes
1 answer
3
VS asked Jan 14, 2018
933 views
A balanced binary search tree of n nodes,the number of steps needed to find and remove the 9th largest element in the worst case?(Please mention the algorithm followed)