CODEWITHSUNDEEP
javabinary-search-tree
SEJAL PITHADIA
SEJAL PITHADIA

Reputation: 21

Maximum difference between node and its ancestor Java soltion having issue

I am practicing Maximum difference between node and its ancestor Java problem using my own solution which worked fine for smaller test cases. However, this is giving differnt output than expected for one of the larger test case. I am not able to see any issue in the code. Please help spot the issue and correct the code.

class Tree
{
//Function to return the maximum difference between any 
//node and its ancestor.
int maxDiff(Node root)
{
    List<Integer> diffs = new ArrayList<Integer>();
    diffs = processNode(root,diffs);
    //diffs.forEach(e -> System.out.println(e));
    return Collections.max(diffs);
    
    //your code here
    
}

public List<Integer> processNode(Node root,List<Integer> diffs){
    if(root.left != null){
        diffs.add(root.data - root.left.data);
        diffs = processNode(root.left,diffs);
    } 
    if(root.right != null){
        diffs.add(root.data - root.right.data);
        diffs = processNode(root.right,diffs);
    }
    return diffs;
}
}

Upvotes: 1

Views: 50

Answers (1)

Marce Puente
Marce Puente

Reputation: 464

As Lajos Arpad indicates you in his answer, the problem of your code, is that it adds to the list, both the differences going to the right, and to the left, you must discriminate which is going to be the direction and then call the corresponding method, something like this:

public class Tree {

   int maxDiff( Node root ) {
      List<Integer> diffs = new ArrayList<Integer>();
      diffs = processLeftNode( root, diffs );
      diffs = processRightNode( root, diffs );
      return Collections.max( diffs );
   }

   public List<Integer> processLeftNode( Node root, List<Integer> diffs ) {
      if( root.left != null ) {
         diffs.add( root.data - root.left.data );
         diffs = processLeftNode( root.left, diffs );
      }
      return diffs;
   }

   public List<Integer> processRightNode( Node root, List<Integer> diffs ) {
      if( root.right != null ) {
         diffs.add( root.data - root.right.data );
         diffs = processRightNode( root.right, diffs );
      }
      return diffs;
   }
}

Upvotes: 0

Related Questions