we have started implementing the Entry class that would be used by a binary sear

Question

we have started implementing the Entry class that would be used by a binary search tree. You need to complete the numberLargerNodesInSubtree and numberSmallerNodesInSubtree methods so that they return the number of nodes in the subtree with elements larger and smaller than the current node's element, respectively .

I do rate the answer, so please answer as accurate as possible, thank you!

---------------------------------------------------------------------------------------------------------------------------------------------------------

Explanation / Answer

count nodes greater tha current node

public int numberLargerNodesInSubtree() {
   return numberLargerNodesInSubtreeUtil(this, this.element);
}
public int numberLargerNodesInSubtreeUtil(BSTEntry node, E key){
   if (node == null) {
       return 0;
   }

   int countLeft = numberLargerNodesInSubtreeUtil(node.left, key);
   int countRight = numberLargerNodesInSubtreeUtil(node.right, key);
return ( (node.element.compareTo(key) >0 )? 1 : 0) + countLeft + countRight;
}

count nodes less than current node

public int numberSmallerNodesInSubtree() {
   numberSmallerNodesInSubtreeUtil(this,this.element);
}
public int numberSmallerNodesInSubtreeUtil(BSTEntry node, E key){
   if (node == null) {
       return 0;
   }

   int countLeft = numberSmallerNodesInSubtreeUtil(node.left, key);
   int countRight = numberSmallerNodesInSubtreeUtil(node.right, key);
return ( (node.element.compareTo(key) <0 )? 1 : 0) + countLeft + countRight;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.