Skip to content
Advertisement

Count nodes that are bigger than all their sons

I have to make a programm that counts the nodes bigger than their sons without including the leaf nodes for example:

4     For this tree, the solution would be 4 because is greater than its son 3 but
     3 is not counted
  3

This is my approach:

   //Result2 is a class that stores a T value (info of the node) and n (counter) to     
   // count the nodes that are bigger than it's sons, this is a method into the class of 
   //the node that is a generic class of binary nodes for trees (left, right and info 
   //parameters)

public Result2<T> countBigger() 
{
    Result2<T> result = new Result2<T>();
    result.info = this.info;
    
    if(this.isLeaf()) 
    {
        result.n = 0;
    }
    else 
    {
        Result2<T> resultL = new Result2<T>();
        Result2<T> resultR = new Result2<T>();
        if(this.hasLeft()) 
        {
            resultL = this.left.countBigger();
        }
        else 
        {
            resultL.info = this.info;
        }
        if(this.hasRight()) 
        {
            resultR = this.right.countBigger();
        }
        else 
        {
            resultR.info = this.info;
        }
        if(result.info.compareTo(resultL.info) > 0 & result.info.compareTo(resultR.info) > 0) 
        {
            result.n++;
        }
        result.n = result.n + resultL.n + resultR.n;
    }
    return result;
}

But I can’t see the error

Advertisement

Answer

Assuming info is an int, this could work for you. I haven’t tested the code, so let me know if there are issues.

public Result2<T> countBigger() {
  Result2 <T> result = new Result2<T>();
  result.info = this.info;

  if (this.isLeaf()) {
    result.n = 0;
  } else {
    Result2<T> resultL;
    Result2<T> resultR;
    
    if (this.hasLeft()) {
      resultL = this.left.countBigger();
    }

    if (this.hasRight()) {
      resultR = this.right.countBigger();
    }
    
    //if resultL/resultR is not set, then there are no children.
    int left = (resultL != null) ? resultL.info ? 0;
    int right = (resultR != null) ? resultR.info ? 0;

    // if parent.info is bigger than both child's info combined, add 1
    // if you want to cout it seprately, then use (result.info > left && result.info > right)
    if (result.info > (left + right)) {
      result.n++;
    }
    
    //Add the counter from child results if they are not null
    result.n += (resultL != null) ? resultL.n : 0;
    result.n += (resultR != null) ? resultR.n : 0;
    
  }
  return result;
}

User contributions licensed under: CC BY-SA
3 People found this is helpful
Advertisement