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 in-order
traversal? I know that given 'n' nodes, number of BTs possible is
(2^n)-n. But if we are given a specific in-order sequence, can we cut
down on this number?| Report Duplicate | Flag | PURGE
Google
Finding median on individual machines can be done using the median-of-median 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 2-D 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.
- 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^(n-1). Given a sequence say - "123" which represents the in-order 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
-1 : The problem is to compute all the binary trees, not just the sum.
- Bugaboo January 11, 2012