Issue
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);
}
}
}
Solution
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);
}
}
}
Answered By - user1984
