bose.debasish
BAN USERAgree with amshali. Can be done with an "augmented" BST.
T(n) = O(log(n) + log(n-1) + ...) = O(log(n!)) ~ O(nlogn)
In worst case its O(n2)
Apology for repeated posts. CareerCup was showing internal error, but post got submitted !!
- bose.debasish February 24, 2012//BC not checked properly
del_min <- INFINITY
p <- root
p_min <- root
while (p)
del_p = (p->val - K)
p_min_dash = p, del_min_dash = del_p
//Tackle left
if (p->left)
del_l = (p->left->val - K)
if (abs(del_l) < abs(del_p))
del_min_dash = abs(del_l)
p_min_dash = p->left
//Tackle right
if (p->right)
del_r = (p->right->val - K)
if (abs(del_r) < abs(del_p))
del_min_dash = abs(del_r)
p_min_dash = p->right
// Tackle root, left, right
if (del_min_dash < del_min)
del_min = del_min_dash
p_min = p_min_dash
//Traverse
if (p_min_dash == p)
if ((p->left) && ((del_p XOR del_l < 0))
p = p->left
if ((p->right) && ((del_p XOR del_r < 0))
p = p->right
else
if (p_min_dash == p->left)
p = p->left
else
p = p->right
end
end
end //end p
//BC not checked properly
del_min <- INFINITY
p <- root
p_min <- root
while (p)
del_p = (p->val - K)
p_min_dash = p, del_min_dash = del_p
//Tackle left
if (p->left)
del_l = (p->left->val - K)
if (abs(del_l) < abs(del_p))
del_min_dash = abs(del_l)
p_min_dash = p->left
//Tackle right
if (p->right)
del_r = (p->right->val - K)
if (abs(del_r) < abs(del_p))
del_min_dash = abs(del_r)
p_min_dash = p->right
// Tackle root, left, right
if (del_min_dash < del_min)
del_min = del_min_dash
p_min = p_min_dash
//Traverse
if (p_min_dash == p)
if ((p->left) && ((del_p XOR del_l < 0))
p = p->left
if ((p->right) && ((del_p XOR del_r < 0))
p = p->right
else
if (p_min_dash == p->left)
p = p->left
else
p = p->right
end
end
end //end p
If the input array contains duplicate values, "augmented", order statistics (BST/Red-Black) tree is better choice than merge sort, as it's not stable.
- bose.debasish February 28, 2012