@all : this little bit different question , but kinda related to it
i am getting segmentation fault in one test case .. but not able to figure
out why it is happening
little help required.
question is , given a BST find floor of a given key.
inorder of BST = 10 20 30 40 50
key = 2
output: floor= 20
now if i give key = 5 , output should be floor=0;
but i am getting segmentation fault for test case.
here is the code:-
int findFloor(node *root,node **floor,int key)
{
int left;
if(!root)
return 1;
if(!findFloor(root->left,floor,key))
return 0;
if(root->data==key)
{
(*floor)=root;
return 0;
}
if(key < root->data)
{
return 0;
}
(*floor)=root;
return findFloor(root->right,floor,key);
}
Thanks in advance
On Tue, Feb 21, 2012 at 8:25 AM, Supraja Jayakumar <suprajasank...@gmail.com
> wrote:
> :) Apologize for the mistake - it is a BST.
>
> Thank You
>
>
> On Mon, Feb 20, 2012 at 7:46 PM, Gene <gene.ress...@gmail.com> wrote:
>
>> The topic of the discussion is:
>>
>> Finding closest double in a Btree
>>
>> A binary tree that is also a B-Tree is (roughly) a Binary Search
>> Tree.
>>
>>
>>
>> On Feb 20, 9:37 pm, Dave <dave_and_da...@juno.com> wrote:
>> > @Gene: I don't know what is confusing about the OP's problem
>> > statement:
>> >
>> > "Question is given a binary tree and a key K, code to find the node
>> > with the
>> > closest value."
>> >
>> > What do you find confusing about that?
>> >
>> > Are you opposed to using shorthand in the subject line that is then
>> > clarified in the body of the posting?
>> >
>> > Dave
>> >
>> > On Feb 20, 8:19 pm, Gene <gene.ress...@gmail.com> wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > Sure the algorithm works for any binary tree, but a B-Tree is a more
>> > > general data structure. So the problem statement is confusing. This
>> > > is probably the reason some people gave alternatives that only work
>> > > with a BST. A BST is a special case of a B-Tree.
>> >
>> > > On Feb 20, 8:58 pm, saurabh singh <saurab...@gmail.com> wrote:
>> >
>> > > > @gene probably you are saying this on the basis of the subject of
>> the
>> > > > mail?Please read the problem statement stated in the mail.Even its
>> a B
>> > > > tree doesn't effects the algorithm proposed by don which says
>> *traverse
>> > > > each node and keep track of minimum.*
>> > > > So irrespective of the data structure used this solution is bound to
>> > > > work....
>> > > > closest:
>> > > > arguments: dataStructure T,int number
>> >
>> > > > tmp:=getelem(T);
>> > > > min=tmp.value
>> > > > while( getelem returns non null values)
>> > > > do
>> > > > nxt:=getelem(T);
>> >
>> > > > if(abs(nxt.value-number)<min) then
>> > > > tmp=nxt
>> > > > min=nxt.value
>> > > > done
>> >
>> > > > done
>> >
>> > > > return tmp
>> >
>> > > > The nextelem function can be written according to the data
>> structure used.
>> >
>> > > > Saurabh Singh
>> > > > B.Tech (Computer Science)
>> > > > MNNIT
>> > > > blog:geekinessthecoolway.blogspot.com
>> >
>> > > > On Tue, Feb 21, 2012 at 6:06 AM, Gene <gene.ress...@gmail.com>
>> wrote:
>> > > > > Not to mention the subject line seems to be asking about B-Trees,
>> > > > > which is no kind of binary tree, so the OP gets it wrong, too.
>> >
>> > > > > On Feb 20, 7:28 pm, Dave <dave_and_da...@juno.com> wrote:
>> > > > > > @Don: By that measure, it also is trivial if the tree is a BST.
>> You
>> > > > > > just find the largest node < x and the smallest one > x and
>> choose
>> > > > > > between them.
>> >
>> > > > > > But since the original problem did not specify a BST, your
>> solution is
>> > > > > > non-responsive. If I were grading a test, I'd have to count your
>> > > > > > solution as wrong, figuring that you do not know the difference
>> > > > > > between a binary tree and a binary search tree.
>> >
>> > > > > > Dave
>> >
>> > > > > > On Feb 20, 5:13 pm, Don <dondod...@gmail.com> wrote:
>> >
>> > > > > > > Yes, I am assuming a binary search tree. The problem is
>> trivial
>> > > > > > > otherwise.
>> > > > > > > If it is just a binary tree, you visit each node and keep
>> track of the
>> > > > > > > closest.
>> > > > > > > Don
>> >
>> > > > > > > On Feb 20, 5:02 pm, Dave <dave_and_da...@juno.com> wrote:
>> >
>> > > > > > > > @Don: Aren't you assuming a binary _search_ tree? Only a
>> binary tree
>> > > > > > > > was specified by the OP.
>> >
>> > > > > > > > Dave
>> >
>> > > > > > > > On Feb 20, 10:44 am, Don <dondod...@gmail.com> wrote:
>> >
>> > > > > > > > > Supraja,
>> >
>> > > > > > > > > I think that your solution will work, but it does more
>> work than is
>> > > > > > > > > necessary. You don't need to traverse the entire tree.
>> >
>> > > > > > > > > node findClosest(node root, double k)
>> > > > > > > > > {
>> > > > > > > > > node result = root;
>> > > > > > > > > double diff = fabs(root->value - k);
>> > > > > > > > > for(node loc = root; loc; loc = (loc->value > k) ?
>> loc->left :
>> > > > > loc->right)
>> >
>> > > > > > > > > {
>> > > > > > > > > double newDiff = fabs(loc->value - k);
>> > > > > > > > > if (newDiff < diff)
>> > > > > > > > > {
>> > > > > > > > > result = loc;
>> > > > > > > > > diff = newDiff;
>> > > > > > > > > }
>> > > > > > > > > }
>> > > > > > > > > return result;
>> >
>> > > > > > > > > }
>> >
>> > > > > > > > > On Feb 20, 5:24 am, Supraja Jayakumar <
>> suprajasank...@gmail.com>
>> > > > > > > > > wrote:
>> >
>> > > > > > > > > > Hi
>> >
>> > > > > > > > > > Question is given a binary tree and a key K, code to
>> find the
>> > > > > node with the
>> > > > > > > > > > closest value.
>> >
>> > > > > > > > > > I'd be happy to receive some feedback about my solution
>> too.
>> >
>> > > > > > > > > > Pls find the code below:
>> >
>> > > > > > > > > > class FindingClosestNodeInTree {
>> > > > > > > > > > private static double difference = 0.0;
>> > > > > > > > > > private static doule key = 0.0;
>> > > > > > > > > > int main() {
>> > > > > > > > > > BinaryTree bt;
>> > > > > > > > > > bt.insert(20.43);
>> > > > > > > > > > bt.insert(12.78);
>> > > > > > > > > > bt.insert(19.89);
>> > > > > > > > > > bt.insert(32.69);
>> > > > > > > > > > bt.insert(2.54);
>> > > > > > > > > > cout << "Please provide the key value" << endl;
>> > > > > > > > > > cin >> key;
>> > > > > > > > > > const Node &closestNode = closestValue(bt);
>> > > > > > > > > > cout << << "Node that has the closest value to " <<
>> <<
>> > > > > > > > > > closestNode.value;
>> > > > > > > > > > return 1;}
>> >
>> > > > > > > > > > const Node & closestValue(const BinaryTree &node) {
>> > > > > > > > > > if(node==null)
>> > > > > > > > > > return;
>> >
>> > > > > > > > > > int val = node.value;
>> > > > > > > > > > int currDiff = val > key ? val-key:key-val;
>> > > > > > > > > > difference = currDiff > difference ?
>> currDiff:difference;
>> > > > > > > > > > if(node.left!=null)
>> > > > > > > > > > closestValue(node.left);
>> > > > > > > > > > if(node.right!=null)
>> > > > > > > > > > closestValue(node.right);
>> > > > > > > > > > return difference;
>> >
>> > > > > > > > > > }
>> > > > > > > > > > }
>> >
>> > > > > > > > > > Thanks
>> > > > > > > > > > Supraja J- Hide quoted text -
>> >
>> > > > > > > > - Show quoted text -
>> >
>> > > > > --
>> > > > > You received this message because you are subscribed to the
>> Google Groups
>> > > > > "Algorithm Geeks" group.
>> > > > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > > > To unsubscribe from this group, send email to
>> > > > > algogeeks+unsubscr...@googlegroups.com.
>> > > > > For more options, visit this group at
>> > > > >http://groups.google.com/group/algogeeks?hl=en.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> U
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
