Trying to understand why this code for a recursive bounded inorder traversal won't work?-CodePudding

I am having trouble understanding how to see if the node I am going over is within the bounds given. After seeing that I am supposed to call the consumer to process each entry in the traversal. An example test case would be A lowerBound of 11 and an upperBound of 64 while traversing this tree It should have a visitation order of [11, 21, 23, 24, 27, 41, 52, 53, 62, 64]

I need help figuring out how I get the helper method to give the rootNode while also giving the lower and upperBound.

   public void boundedInorderTraverse(Consumer<T> consumer) {
      boundedInorderTraverse(getRootNode(), consumer);
   }
   public void boundedInorderTraverse(T lowerBound, T upperBound, Consumer<T> consumer) {
      //BinaryNode<T> node = getRootNode();
   
      if(node != null) {
         
         if(node.getLeftChild().getData().compareTo(lowerBound) >= 0 && node.getLeftChild().getData().compareTo(upperBound) <= 0) {
            boundedInorderTraverse(lowerBound, upperBound, consumer);
            consumer.accept(node.getData());
         }
         consumer.accept(node.getData());
         if(node.getRightChild().getData().compareTo(lowerBound) >= 0 || node.getRightChild().getData().compareTo(upperBound) <= 0) {
            boundedInorderTraverse(lowerBound, upperBound, consumer);
            consumer.accept(node.getData());
         }
      }
   } // end inorderTraverse

CodePudding user response：

 public void boundedInorderTraverse(T lowerBound, T upperBound, Consumer<T> consumer) {
      BinaryNode<T> currentNode = getRootNode();

This is a recursive algorithm; while the first time it's run it will be starting from the root, that's not the case every time. You should have currentNode as an argument to the function, call it on getRoodNode() from the call site (maybe make a helper function to set up the initial call), and then pass the left or right children for the recursive calls.

   
      if(currentNode == null) {

Pretty sure the above current == null is a typo, so fix that.

         BinaryNode<T> temp = currentNode.getLeftChild();
         if(temp.getData().compareTo(lowerBound) >= 0 || temp.getData().compareTo(upperBound) <= 0) {

|| there implies you accept anything that's over the lower bound OR over the upper bound - assuming the upper is greater than the lower, that's everything.

Also, Using <= in both cases says that you're including both upper and lower bound. Usually it's standard to include the lower bound but not the upper. That's not a 100% rule but check the requirements to make sure.

         boundedInorderTraverse(lowerBound, upperBound, consumer);
         consumer.accept(currentNode.getData());

"In-Order" means you check the left, then the parent, then the right. You check both children in the recursive call, so this means you're checking the left, then the right, then the parent, which would be post-order.

         }
         temp = currentNode.getRightChild();
         if(temp.getData().compareTo(lowerBound) >= 0 || temp.getData().compareTo(upperBound) <= 0) {
         boundedInorderTraverse(lowerBound, upperBound, consumer);
         consumer.accept(currentNode.getData());
         }

Don't forget to fix all of the same issues in the right-child block as well as the left.

         
      }
   }

The above section is fine.

To explain further on the current thing, you just need an entry point that finds the root and passes the other arguments through:

public void entryMethod(T lowerBound, T upperBound, Consumer<T> consumer) {
   BinaryNode<T> start = getRoodNode();
   boundedInorderTraverse(start, lowerBound, upperBound, consumer);
}

public void boundedInorderTraverse(BinaryNode<T> currentNode, T lowerBound, T upperBound, Consumer<T> consumer) {
    ...
}