Question

Implement a function named printRange that, given the pointer to the root of a BST, a low key value, and a high key value, prints in sorted order all records whose key values fall between the two given keys (inclusive). Function printRange should visit as few nodes in the BST as possible. Here is the start code (in Java 8) for this problem. Input Format Three lines. The first line includes the number of keys to be put in the BST, and the second line includes the actual numbers. The third line includes two numbers, for low key and high key, respectively. Constraints The keys are integers. Output Format The key values that fall between the two given low and high keys, in sorted order. Sample Input 0 10 39 78 10 99 79 48 93 58 73 83 5 98 Sample Output 0 10 39 48 58 73 78 79 83 93

start code

import java.util.Scanner;
	class Node {
	private Node left;
	private Node right;
	private int data;
	Node(int data) {
	this.data = data;
	left = null;
	right = null;
	}
	void setData(int d) {
	data = d;
	}
	int getData() {
	return data;
	}
	void setLeft(Node i) {
	left = i;
	}
	void setRight(Node i) {
	right = i;
	}
	Node getLeft() {
	return left;
	}
	Node getRight() {
	return right;
	}
	}
	class PrintRange {
	public static Node insert(Node root, int data) {
	if (root == null) {
	return new Node(data);
	} else {
	Node cur;
	if (data < root.getData()) {
	cur = insert(root.getLeft(), data);
	root.setLeft(cur);
	} else {
	cur = insert(root.getRight(), data);
	root.setRight(cur);
	}
	return root;
	}
	}
	//implement printRange() function
	public static void printRange(Node root, int low, int high) {
	}
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int t = scan.nextInt();
	Node root = null;
	while (t-- > 0) {
	int data = scan.nextInt();
	root = insert(root, data);
	}
	int low = scan.nextInt();
	int high = scan.nextInt();
	scan.close();
	printRange(root, low, high);
	}
	}

Answer 1

THE CODE FOR THE ABOVE QUESTION IS :

import java.util.Scanner;

class Node {

    private Node left;
    private Node right;
    private int data;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }

    void setData(int d) {
        data = d;
    }

    int getData() {
        return data;
    }

    void setLeft(Node i) {
        left = i;
    }

    void setRight(Node i) {
        right = i;
    }

    Node getLeft() {
        return left;
    }

    Node getRight() {
        return right;
    }
}

class PrintRange {

    public static Node insert(Node root, int data) {
        if (root == null) {
            return new Node(data);
        } else {
            Node cur;
            if (data < root.getData()) {
                cur = insert(root.getLeft(), data);
                root.setLeft(cur);
            } else {
                cur = insert(root.getRight(), data);
                root.setRight(cur);
            }
            return root;
        }
    }

    //implement printRange() function
    public static void printRange(Node root, int low, int high) {

        // base case
        if (root == null) {
            return;
        }

        // Since the output should be in sorted order while visiting
        // as fewer nodes as possible to achieve the task.
        // We recursively first visit the left subtree and print all values
        // which are greater than low in the left subtree. Therefore if low
        // is greater than the value at the root node then there will be no values
        // in the left subtree greater than low.
        if (low < root.getData()) {
            printRange(root.getLeft(), low, high);
        }

        // Now if the value present at the current node lies in the range of
        // low and high (inclusive) we print it.
        // This statement is executed only when we have traversed upto the point
        // where the value at node is less than low for the left subtree &
        // similarly for the right subtree upto the node where the value is greater
        // than high.
        if (low <= root.getData() && high >= root.getData()) {
            System.out.print(root.getData() + " ");
        }

        // If the value present in the current node is smaller than high then
        // only we recurse the right subtree.
        if (high > root.getData()) {
            printRange(root.getRight(), low, high);
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        Node root = null;
        while (t-- > 0) {
            int data = scan.nextInt();
            root = insert(root, data);
        }
        int low = scan.nextInt();
        int high = scan.nextInt();
        scan.close();
        printRange(root, low, high);
    }
}

SAMPLE OUTPUT #1 :

SAMPLE OUTPUT #2 :