Bugaboo
BAN USER 1of 3 votes
AnswersGiven an inorder traversal only for a binary tree (not necessarily a
 Bugaboo in United States
BST), give a pseudo code to generate all possible binary trees for
this traversal sequence.
Firstly, how many binary trees can be generated given an inorder
traversal? I know that given 'n' nodes, number of BTs possible is
(2^n)n. But if we are given a specific inorder sequence, can we cut
down on this number? Report Duplicate  Flag  PURGE
Google
Finding median on individual machines can be done using the medianofmedian algorithm in O(n) time [n  # of elements one a single machine]
The overall median must lie between Min(median1,median2,....mediani) and Max(median1,median2,....mediani).
 Therefore, eliminate all elements less than Min(median1,median2,....mediani) and greater than Max(median1,median2,....mediani). Repeat the above steps again till you are left with 3 (or 4 elements)
 Sort these small number of elements to obtain the overall median.
I'm assuming that the median for even number of elements (say, m) is either A[m/2] or A[m/2+1].
 1st iteration:
1 2 8 14 > 2,8
3 6 15 17 > 6,15
5 9 18 20 > 9,18
7 11 19 21 > 11,19
The median of the 2D array must lie between [2,19]. Eliminate all elements lesser than 2 and greater than 19 (which is 1, 20, 21) in this case.
Repeat again finding median for the rows again.
You will end up with '9' as the median.

Bugaboo
January 02, 2012  This is similar to finding the median of 2 sorted arrays. Can extend the same divide and conquer technique here.
 Find the median of all rows (Say m1,m2,m3 for 3X5 matrix)
 The overall median should lie b/w Min(m1,m2,m3) and Max(m1,m2,m3)
 Eliminate all elements from each row which does not lie in the above range
 Repeat above steps once again until the input becomes small enough to sort and pick the median (since sorting smaller set of elements like 4 elements take constant time)
Worst case time complexity will be O(n^3) [for a square matrix]
Best case time complexity will be O(nlog n) [Input size always divides by half]
I can understand a bit of what you mentioned about the tree construction but I don't agree to 2^(n1). Given a sequence say  "123" which represents the inorder traversal of a BT (not necessarily a BST), the number of binary trees possible are only 3 (which is equal to the length of the string  n)
Possible trees:
1 2 3
\ / \ /
2 1 3 2
\ /
3 1

Bugaboo
December 28, 2011 Open Chat in New Window
1 : The problem is to compute all the binary trees, not just the sum.
 Bugaboo January 11, 2012