Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Devaka Cooray
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Knute Snortum
  • Bear Bibeault
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Frits Walraven
  • Carey Brown
  • Tim Holloway

Understanding how Successors and Predecessors work in code.

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone!
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.

 
Bartender
Posts: 2219
47
IntelliJ IDE Firefox Browser Spring Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch!
I have moved your topic to Java in General forum as it is more appropriate place for your question.
Ranch Office is a place for topics about the Ranch itself.
 
Saloon Keeper
Posts: 10308
217
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Amelia, welcome to CodeRanch!

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()".
  •  
    It is sorta covered in the JavaRanch Style Guide.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!