0

I have a Tree class that has a nested private Node class.
I wrote a method (Search(T elem)) that searches if the element given as parameter exists in the tree and sends a boolean.
However my problem is that this method only sends true if the element exists in the first branch of my tree and if not, it sends false. I must have mistaken somewhere in recursive calls.

for example, here in main i call search('C') and I get false although I should get true because C is in the second branch of my tree.
P.S. : Also I should mention that in this class, copy operator and constructor must be disabled and i can not use anything but raw pointer (no vector or smart pointers).
Thank you in advanced.

  • It's time to learn how to debug your code. – Thomas Sablik Nov 11 '19 at 20:43
  • @ThomasSablik I debuged it and I understood that the problem is with my recursive call but I don't know how to fix it .......... :))) –  Nov 11 '19 at 20:50
  • _"somewhere in recursive calls"_ doesn't sound like you debugged the code and found the reason for the problem. If you debugged your code and know the problem please add this information to your question. – Thomas Sablik Nov 11 '19 at 20:54
  • Your problem is pretty similar to https://stackoverflow.com/questions/58808623/how-to-compare-new-string-name-with-existing-from-txt-file. If you understand the other problem you will understand your problem. – Thomas Sablik Nov 11 '19 at 21:25

1 Answers1

1

You shouldn't return children[i]->search(elem); directly. So it will return false if elem is not found in the first branch, it will never get past the first child. Only return there directly if it is found. Otherwise try the other children.

n314159
  • 4,990
  • 1
  • 5
  • 20
  • sorry but I din't quite get what you are saying. could you pleas be more specific. Thank you –  Nov 11 '19 at 20:54
  • Consider the case where your tree only has the root with two children. Try to work through your code and think about what happens, when `elem` is in the second child. – n314159 Nov 11 '19 at 20:57
  • @Mohammadreza `if (children[i]) return children[i]->search(elem);` checks the first child and exits the loop. It doesn't check the other children. – Thomas Sablik Nov 11 '19 at 21:00
  • @ThomasSablik but doesn't the recursive call to method do the trick to search in all children ???? Are you saying that there is something wrong with `return` in this method –  Nov 11 '19 at 21:05
  • @Mohammadreza Do what n314159 said. Create a tree with root and two children. The character should be in the second child node. Run the program in your debugger and you will see exactly where the problem is. n314159 also described a solution. You should only return the value if it is true. Otherwise stay in the loop. `return` exits the loop and the function even if not all children where checked – Thomas Sablik Nov 11 '19 at 21:19
  • @ThomasSablik ok i will try what happens in debugger. Thank you. Also, regarding the `return false`, is it in good place. Because if I don't write it there, I get a warning –  Nov 11 '19 at 21:25
  • @Mohammadreza Yes, it's in a good place. It's the only place where you can return false. Anywhere else in the function you can only return true. – Thomas Sablik Nov 11 '19 at 21:28
  • @ThomasSablik so I do this `bool search(T elem) { if (_info){ // if (_info->getData() == elem) return true; Tree** children = _info->getChildren(); for (char i = 0; i < N; i++){ if (children[i]){ if (children[i]->_info->getData() == elem) return true; children[i]->search(elem); } } } return false; }` and I am able to search for second children of the root but i can not search for children of the children of the root. I am stuck in the first level of my tree –  Nov 11 '19 at 21:36
  • @ThomasSablik I am very struggling here to see where comes the problem, i tried to debug with gdb to see where from comes the problem but i was not successful to find it –  Nov 11 '19 at 21:37
  • You are stuck in the first level since you do nothing with the output of your recursive function call. You have to utilise the value of `children[i]->search(elem);` – n314159 Nov 11 '19 at 21:42
  • 1
    @Mohammadreza change `if (children[i]) return children[i]->search(elem);` to `if (children[i] && children[i]->search(elem)) return true;` in your original code. – Thomas Sablik Nov 11 '19 at 21:42
  • @ThomasSablik n314159 Thanks for help ... i see now what is happening and where I was not stupidly looking. –  Nov 11 '19 at 21:46