Java BST recursion variable setting

Question

I have a normal binary search tree implemented with a string value for data, and right and left nodes. The tree works fine but I am having trouble with my rankOf function. I use recursion to find the nodes and the method is successful when the element exists, but when a value not present is does not work and I can't figure out how to set a boolean within to help with this. Here is the code:

private int rankOf(String s, Node n){ if (n != null){ //check root if (s.compareTo(n.value) == 0){ if (n.left != null){ return size(n.left); } return 0; } // only worry about left tree, easy if (s.compareTo(n.value) < 0){ return rankOf(s, n.left); } else { // must count entire left tree plus root node return rankOf(s, n.right) + size(n.left) + 1; } } //null or not found return 0; }

When root is equal to the value I know the element is in the tree so something should go in there but unsure how to handle this.

"but when a value not present is does not work" it throws an exception ? pls post your tree — CodeIsLife
– CodeIsLife, Commented Oct 21, 2017 at 22:51
What does your size method return ? Also what should your method return in case of success/failure ? — Schidu Luca
– Schidu Luca, Commented Oct 21, 2017 at 23:02
@SchiduLuca Size returns the amount of nodes on the subtree of the node passed. It can just return -1 if failure. — User 965
– User 965, Commented Oct 21, 2017 at 23:36
@CodeIsLife It wont throw an exception it will just return the rank as if the value was present. For instance if the tree contains A, B, and C, and you try to find the rank of D it will return 3 (3 nodes smaller than D) even though D isn't in the tree. — User 965
– User 965, Commented Oct 21, 2017 at 23:38

Schidu Luca · Accepted Answer · 2017-10-22 10:17:12Z

This checking is useless:

if (n.left != null){ return size(n.left); }

Anyway, you can do something like this:

static int rankOf(String s, Node root) { if(root == null) { return -1; } if(root.value.equals(s)) { return size(root); } int result; if(s.compareTo(root.value) > 0) { result = rankOf(s, root.right); } else { result = rankOf(s, root.left); } return result; }

And your size() method:

static int size(Node root) { if(root == null) return 0; return size(root.left) + size(root.right) + 1; }

In case the String is not found, -1 will be returned.

Collectives™ on Stack Overflow

Java BST recursion variable setting

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related