I know how to find Successors and Predecessors in a Binary Search Tree but I'm having a small problem understanding how they work in coding.
The following code works perfectly but could someone explain to me what happens in each step.Thanks in advance.
Do you know how recursion works? It's not very hard when you get a feel for it, but it may be difficult to make it 'click' at first. The trick is that a recursive function works on a large problem by making it smaller and then reapplying itself to those smaller problems. Let's take the following problem: "Return all ints in a binary tree using in-order traversal". This problem can be solved by "returning the value of the root, and then return all values in the left sub-tree, and then return all values in the right sub-tree". Here's how you would start out:
If only we had some magic method that could return all values in a tree... Wait, we do! It's called getAllValuesInOrder()! We can just use it inside its own definition:
You see that returning the values in the left tree and in the right tree is the same problem as returning all values in the whole tree, only smaller? This means we can reapply the function to these sub-trees. The problem is, when do we stop? What happens when you try to get the values of a null tree? Every recursion needs a base case: The simplest problem for which you can explicitly return a result without going deeper.
If you understand all of this, try to explain what the the problem is in your code that you're trying to solve, and try to identify what the "smaller problems" are that it consists of. You should also try to identify the "simplest case".
Please keep in mind that there are some problems with that code which can make it more unclear:
It uses static variables to return a method result.
The method is a utility method, but isn't declared static.
The method is not named after a verb. Methods should be named after what they do, such as "findSuccessor()".