killbot
BAN USERO(n) space and time in C
Using column ID diff from root as the hash key. Root will be column 0, one on the left will be column-1 and for right it will be column+1. Using pre-order traversal to assign column ID to each element and then inserting the elements in the hash. Due to pre-order traversal the column ordering is maintained within the hash buckets.
#include <stdio.h>
ehash_t hash;
int min_column = 0;
int max_column = 0;
void compute_column(node_t* node, int current_column)
{
if (current_column < min_column) {
min_column = current_column;
} else if (current_column > max_column) {
max_column = current_column;
}
hash.insert(current_column, node->data);
if (node->left != NULL) {
compute_column(node->left, current_column - 1);
}
if (node->right != NULL) {
compute_column(node->right, current_column + 1);
}
}
void print_columns()
{
for (int i = min_column; i < max_column; ++i)
{
hash.print(i);
}
}
int main(int argc, char const *argv[])
{
compute_column(root, 0);
print_columns();
return 0;
}
This solution is very close to what Diptesh has mentioned.
Posting it in C.
O(n) time complexity
First we need to determine the size of the S array.
We will be solving for P length = n*(n-1)/2
Which is x*y = 2*len(P) && x-y = 1 where x is the length of S.
We will also use the length to compute each entry in S.
eg.
P = {x1+x2, x1+x3, ...., x2+x3}
adding first 2 and subtracting the first sum of the next element.
2x1+x2+x3-(x2+x3) = 2x1
We will do this until we hit the last element in the P. Which is the only sum for last two elements in S.
Special case for the last two elements in S.
We will use the last two sums to compute P[i-2] & P[i-1] and subtract the known last element.
eg.
P = {....x2+x3,x2+x4,x3+x4}
So far our S computed will be
S = {x1,x2}
So we will subtract last known element from the last two sums
x2+x3 - x2 = x3
&&
x2+x4 - x2 = x4
- killbot April 04, 2016