Print BST keys in the given range-CodePudding

I am wondering what is wrong with my method of printing the BST keys in the given range [min, max]. Given the class

public class BinarySearchTree<E extends Comparable<? super E>> {
   private Node<E> root;
    
   // Constructors and other methods
    
   private static class Node<E> {
      private E data;
      private Node<E> left;
      private Node<E> right;
        
      private Node(E data) {
         data = data;
         left = right = null;
      }
   }
}

what is wrong with this solution:

public void printPart(E min, E max) {
    Print(root, min, max);
}

private void Print(Node<E> n, E min, E max){

    if(n!=null){
        if(n.data.compareTo(min) > 0){ // If node data is greater than min recurse through left subtree
            Print(n.left, min, max);
        }else if(n.data.compareTo(min) >=0 && n.data.compareTo(max) <=0){ // Printing the root if it lies between the given bounderies
            System.out.println(n.data);
        } else{ // recurse through right subtree
            Print(n.right, min, max);
        }
    }

}

CodePudding user response：

The condition of your current algorithm are wrong. You first check:

if(n.data.compareTo(min) > 0){ // If node data is greater than min recurse through left subtree
            Print(n.left, min, max);

Whenever the nodes data is greater than min you recurse through the left subtree. But what if it is greater than min and less than max? Since this is an if... else if... construct the other conditions never hit. So you could potentially miss to print a node that is greater than min and less than max.

Then the second condition is as follows:

        }else if(n.data.compareTo(min) >=0 && n.data.compareTo(max) <=0){ // Printing the root if it lies between the given bounderies
            System.out.println(n.data);

Now, if the node is in the proper interval between min and max, you are only printing it but don't recurse left and right. There could be other nodes that you are missing.

So, in general, the conditions are not correctly written. The following code first checks if the node is in the min/max interval. If so, it traverse left and right and also prints the node. It is an inorder traversal, that's why it first goes left, then prints and then goes right. Then it checks if node is less than min. In that case it recurses right, and otherwise left.

public void printPart(E min, E max) {
    Print(root, min, max);
}

private void Print(Node<E> n, E min, E max){

    if(n!=null){
        if(n.data.compareTo(min) >=0 && n.data.compareTo(max) <=0){ // If node lies in min/max interval: print and recurse both left and right
            Print(n.left, min, max);  // we do an inorder: left, root, right
            System.out.println(n.data);
            Print(n.right, min, max);
        }else if(n.data.compareTo(min) < 0){ // If node less than min, recurse right
            Print(n.right, min, max);
        } else{ // recurse left
            Print(n.left, min, max);
        }
    }

}

CodePudding user response：

First get traversal of the entire tree correct:

private void Print(Node node) {
  if (node == null) return;
  Print(node.left);
  // Visit the node in BST sorted order here.
  Print(node.right);
}

In your case the "visit" is to check whether the node's value lies in the range.

There's not much sense in passing the range through every recursive call. It's verbose and error prone. You can make it a class attribute:

class RangePrinter<E extends Comparable<? super E>> {
  private final E min, max;

  private RangePrinter(E min, E max) {
    this.min = min; this.max = max;
  }

  private void print(Node<E> node) {
     if (node == null) return;
     print(node.left);
     if (min.compareTo(node.data) <= 0 && node.data.compareTo(max) <= 0) 
       System.out.println(node.data);
     print(node.right);
  }

  static <E extends Comparable<? super E>> void Print(Node<E> node, E min, E max) {
    new RangePrinter(min, max).print(node);
  }
}

Use this with RangerPrinter.Print(root, 3, 42);.

Note that this is a naive solution in that you might have a tree with a billion nodes and need to print only 3. This algorithm would visit all billion. A good one would need to visit only a maximum of about 90. But that's trickier to implement (in Java at least)...