deepak.bvp
BAN USER// generates a similar tree with corresponding binary positions
// binary positions are like '101' or '1011' etc
$positionsTreeRoot = formBinaryPositionTree($root);
method getNeighbours($tempRoot,$node, $k){
//getBinaryPosition returns binaryPositons from $positionsTreeRoot
$nodeBinaryPosition = getBinaryPosition($node);
$rootBinaryPosition = getBinaryPosition($tempRoot);
if( getDistance(
$nodeBinaryPosition,
$rootBinaryPosition
) == $k )
print $tempRoot->data
//continue traversal
if($tempRoot->left != NULL)
getNeighbours($tempRoot->left,$node, $k);
if($tempRoot->right != NULL)
getNeighbours($tempRoot->right,$node, $k);
}
/*
$position1 and $position2 are binary
*/
method getDistance($position1, $position2){
//binLength returns length ie, 101 > 3, 1011 > 4
$binLenDiff = binLength($position1) - binLength($position2);
if($binLenDiff < 0)
shift right $position2 abs($binLenDiff) times
else
shift right $position1 abs($binLenDiff) times
//now position1 and position2 are of equal length
$xor = $position1 ^ $position2;
return ( 2* BinLength($xor)) + abs($binLenDiff);
}
mark every node as a binary number,
root -> 1
left node to root -> 10
right node to root -> 11
after that -> 100-101 and 110-111
.. and so on, we will have a tree of binary numbers.
now suppose we want to know distance between '100' and '1011', follow these steps,
1. '100' would be at 'level 2' and '1011' at 'level 3'. Parent of '1011' would be '101' and it's distance '1011' would be '1'. We now have to fine distance between 100 and 101.
2. XOR '100' and '101' => '001'. Position of left most '1' in '001' gives distance of common ancestor. In this case it is '1'.
3. Distance between 100 and 1011 would be 2 * 'common ancestor distance' + ( 1011 <-> 101 distance). which is 2*1 + 1 = 3
So 3 is the distance. This way we can calculate all the distances.
- deepak.bvp December 21, 2013