Using a recursive method to find the smallest element in a subtree given by the root: what am I doing wrong here?
So I have a homework question where I have to use the recursive method to "find the minimum element inside the subtree rooted at the specified node"
And then I'm given this as a starting point:
public TreeNode
{
int data;
TreeNode left;
TreeNode right;
}
and
/**
Finds the minimum value for the subtree that is
rooted at a given node
@param n The root of the subtree
@return The minimum value
PRECONDITION: n is not null.
*/
int min(TreeNode n)
{
// COMPLETE THE BODY OF THIS METHOD
}
Now I have a very simple driver program written to insert nodes into a tree and I wrote my recursive method but it seems to count instead of down, here's my method:
int min(TreeNode n){
if(n.left != null) {
n = n.left;
min(n);
System.out.println("N is now " + n.value);
}
return n.value;
}
Output of my code:
Building tree with rootvalue 25
=================================
Inserted 11 to left of node 25
Inserted 15 to right of node 11
Inserted 16 to right of node 15
Inserted 23 to right of node 16
Inserted 79 to right of node 25
Inserted 5 to left of node 11
Inserted 4 to left of node 5
Inserted 2 to left of node 4
Root is 25
N is now 2
N is now 4
N is now 5
N is now 11
The minimum integer in the given nodes subtree is: 11
Can someone explain to me why this is not working?
source to share
Note: This all assumes you are in a binary search tree, so returning the smallest item means returning the left-most item.
This means that your recursive call is pretty simple:
min(node):
if this node has a left node:
return min(node.left)
if this node does not have a left node:
return this node value
The logic is that if we don't have another left node, then we are the leftmost node, so we are the minimum.
Now, in Java:
int min(TreeNode n){
if (n.left == null)
return n.value;
return min(n.left); // n.left cannot be null here
}
Now, to explain your results, consider how this method works. It calls the method on the next node ( min(n.left)
) before continuing. In your case, after this recursive call you had println
. So println
inside the recursive call I went first. This way your prints started at the bottom of the tree and worked again. This explains the "reverse order" printing.
Then your method returned 11
as a result, because (as another answer explained) yours n = n.left
did not affect any of your recursive subplots, only the one in the current function call. This means you returned the left node of the root, not the farthest left child.
Hope this makes sense. If you need to clarify, leave a comment or something else. Recursion can be quite tricky to get around the head first.
source to share
public static void main(String[] args) throws IOException, NoSuchMethodException, InitializationError {
Logger.getRootLogger().addAppender(new ConsoleAppender(new SimpleLayout(), "System.out"));
Logger.getRootLogger().setLevel(Level.ALL);
TreeNode n1 = new TreeNode();
TreeNode n2 = new TreeNode();
TreeNode n3 = new TreeNode();
TreeNode n4 = new TreeNode();
TreeNode n5 = new TreeNode();
TreeNode n6 = new TreeNode();
n1.data = 110;
n1.left = n2;
n1.right = n3;
n2.data = 15;
n2.left = n4;
n2.right = null;
n3.data = 3;
n3.left = null;
n3.right = null;
n4.data = 4;
n4.left = null;
n4.right = n5;
n5.data = 12;
n5.left = n6;
n5.right = null;
n6.data = 19;
n6.left = null;
n6.right = null;
System.out.print("min=" + min(n1));
}
static public class TreeNode {
int data;
TreeNode left;
TreeNode right;
}
static int min(TreeNode n) {
return min(n, n.data);
}
static int min(TreeNode n, int min) {
System.out.println("N is now " + n.data);
int currentMin = min;
if (n.left != null && n.right != null) {
final int left = min(n.left);
final int right = min(n.right);
if (left < right) {
currentMin = left;
} else {
currentMin = right;
}
} else if (n.left != null) {
currentMin = min(n.left);
} else if (n.right != null) {
currentMin = min(n.right);
}
if (currentMin < min) {
return currentMin;
} else {
return min;
}
}
OUTPUT:
N is now 110
N is now 15
N is now 4
N is now 12
N is now 19
N is now 3
min=3
You need to use tree traversal to check every node of the tree. Also you need to save the current found minimum. Pass this minimum to a recursive function. It calls the "battery".
source to share
The last statement in the method implementation returns the value node n. Since n starts at the root and is replaced by its left child (if exists), you always get the value of the root left child.
The following code should do it:
int min(final Tree n){
int result;
if(n == null){
result = Integer.MAX_VALUE;
} else {
result = n.value;
final int leftResult = min(n.left);
if(leftResult < result){
result = leftResult;
}
final int rightResult = min(n.right);
if(rightResult < result){
result = rightResult;
}
}
return result;
}
Or you can use the visitor template (you will need to make your tree Iterable and pass the values to the visitor one by one):
interface TreeVisitor {
void accept(int value);
}
class MinTreeVisistor implements TreeVisitor {
int min = Integer.MAX_VALUE;
@Override
public void accept(int value) {
if(value < this.min) {
this.min = value;
}
}
}
source to share