Hello, I have a method that looks for an element in a binary tree and the problem is that it behaves incredibly strange. When I went through the debager on it, it turned out that everything works exactly as I had in mind, but after going through the return line, the method does not finish the work, but begins to perform some more incomprehensible actions. It just breaks my understanding of how methods work.

Here is the code:

 @Override public Leaf<E> find(E elem) { Leaf<E> eLeaf = new Leaf<>(elem); return binarySearch(root, eLeaf); } private Leaf<E> binarySearch(Leaf<E> leaf, Leaf<E> eLeaf) { int compare = leaf.compareTo(eLeaf); if (compare < 0 && leaf.right != null) { binarySearch(leaf.right, eLeaf); } if (compare > 0 && leaf.left != null) { binarySearch(leaf.left, eLeaf); } if (compare == 0) { return leaf; } return null; }

To be precise, everything goes fine, but then it finds a match in place:

 if (compare == 0) { return leaf; }

Comes to the line return leaf; everything seems to be all ... The blue stripe of the debugger has gone to return , the debager prints the address of the object to me which will now return ... But no, all of a sudden it returns to the second if ! How is this possible? Does not writing return guarantee that the work of the method will be completed?

  • one
    This is not a binary search - this is a deep search. - Mikhail Vaysman
  • @Mikhail Vaysman Yes, I did not call it well. - Pavel
  • Look more closely at what happens to the call stack - vp_arth

1 answer 1

You have a recursion. Going back to the previous level. Before this, the first method call was made in if . After return is a transition to the second if .

Perhaps it was thought somehow like this:

 private Leaf<E> binarySearch(Leaf<E> leaf, Leaf<E> eLeaf) { int compare = leaf.compareTo(eLeaf); if (compare < 0 && leaf.right != null) { return binarySearch(leaf.right, eLeaf); } if (compare > 0 && leaf.left != null) { return binarySearch(leaf.left, eLeaf); } if (compare == 0) { return leaf; } return null; }
  • one
    and sorry what's the difference? this is a copy of the code that I wrote - Pavel
  • Thank you all so much - Pavel