CODEWITHSUNDEEP
javarecursionbinary-treemax
M.K
M.K

Reputation: 189

comparison of adjacent children in tree does not take place?

What is wrong with this method ? it seems but I am not sure that the comparison of adjacent children in the tree does not take place.

I roughly traced the workings of this algorithm by hand and I think the idea is correct maybe something wrong with the implementation or I have no Idea how recursion works, the second helper (compare) method seems to be the issue

public static int MAX(BST B) {
  int m = ((Integer) B.root.data).intValue();
  return call(B.root, m);
}

public static int call(node current, int max) {   
  //first helper method gets the max from two different levels in the tree
  if(current == null)
    return -1;
  if(current.left == null && current.right == null)
    return max;
  else {
    if(((Integer) current.data).intValue()>max)
      max = ((Integer) current.data).intValue();
    return compare(call(current.left,max),call(current.right,max));
  }
}

//second helper method gets the max
static int compare(int m1, int m2) {
  if(m1>m2)
    return m1;
  else 
    return m2;
}

Upvotes: 1

Views: 123

Answers (3)

Christopher Neylan
Christopher Neylan

Reputation: 8272

Since you are searching the entire tree, I'm going to assume that the structure is not properly ordered.

The bug is in your call function with:

 if(current.left==null&&current.right==null) return max;

Imagine you have a tree with a root with two leaf nodes (three nodes total). The root has value 3, right has value 2, and left has value 5. The algorithm should return 5, but your code will return 3. This is because you ignore the value of any leaf (a node with no "children") with that line of code. So your code ignores the value 5, in this example, and returns max, which is 3.

You can fix this by returning compare(current.value, max) when left and right are null.

Upvotes: 3

user177800
user177800

Reputation:

... I have no Idea how recursion works ...

Recursion means the method you are in gets called from inside itself with some other arguments , and there is some check that exits by returning a value or continues to call itself recursively.

call() is indirectly recursive, as it either exits with a return of -1 or max or it calls itself again with new arguments and continues to do this until it either exits or crashes with an OutOfMemory error as the stack fills up.

This method isn't recursive: It is poorly named though.

static int compare(int m1, int m2) {
  if(m1>m2)
    return m1;
  else 
    return m2;
}

and could be written ( and renamed ) as 

static int min(final int m1, final int m2)
{
    return Math.min(m1,m2);
}

or just inlined into

return Math.min(call(current.left,max),call(current.right,max));

either way, you are getting the minimum of the two values, not really comparing them that implies different logic and a different return value.

Either way that method isn't recursive and if the logic of m1 > m2 is appropriate it can't be the problem, more like the input to that function is not what you expect.

Step debugging is a powerful tool and one all experienced developers use every day!

Upvotes: 0

smitec
smitec

Reputation: 3049

I think (not 100%) that you may have an issue because you only check if BOTH children are null if for example right is null and left is not you will attempt to call the method call on both right and. Perhaps add a case checking if one child is null and if so return call of the non null child.

Upvotes: 0

Related Questions