Stack Based Programs : Need to prepare before an interview

                           Stack Data Structure – Introduction and Implementation

What is Stack??

Stack is an abstract data type (ADT) and very useful in programming.
In computer science, a stack is an abstract data type that serves as a collection of elements.
Majorly all the operations are done at only one end of the stack which is top of the stack.
The order in which elements in stack are stored is with LIFO (Last-in-First-Out) manner. Means the element inserted last will be removed first.

See the diagram below for more understanding.

Operations on Stack and How to Implement:

Java already has a built-in class for Stack. Click here to read about it.

Ways to implement Stack

>  Implement stack using Array (discussed Just below)
>  Implement stack using LinkedList (discussed at last)

Operations:

Initialize a topIndex = -1;

For push() operation- increment topIndex by 1 and add element at this index in array. Time- O(1)
For pop() operation- remove element from the topIndex, decrement topIndex by. Time- O(1)
For peek() operation- return the element from the topIndex. Time- O(1)
For isEmpty() operation- check if topIndex<0 then return true else false. Time- O(1)
For getSize() operation- return the topindex+1. Time- O(1)


PROGRAM:


public class StackUsingArray {
    int size;
    int topIndex = -1;
    int [] stack;

    public StackUsingArray(int size){
        this.size = size;
        stack = new int[size];
    }
    public void push(int num){
        if(topIndex==size-1) {
            System.out.println("Stack overflow, ...cannot insert new element");
            return;
        }
        System.out.println("Inserting " + num +  " into Stack.");
        topIndex = topIndex + 1;
        stack[topIndex] = num;
    }
    public Integer pop(){
        if(topIndex<0) {
            System.out.println("Stack is empty, nothing to pop");
            return null;
        }
        System.out.println("Popping from Stack.");
        Integer x =  stack[topIndex];
        topIndex--;
        return x;
    }
    public Object peek(){
        if(topIndex<0) {
            System.out.println("Stack is empty, nothing to pop");
            return null;
        }
        System.out.println("Popping from Stack.");
        return stack[topIndex];
    }

    public boolean isEmpty(){
        return (topIndex<0);
    }
    public int getSize(){
        return topIndex+1;
    }
    public void displayStack(){
        System.out.print("Stack (top-->bottom): ");
        for (int i = topIndex; i >=0 ; i--) {
            System.out.print(stack[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int size = 4;
        StackUsingArray stack = new StackUsingArray(size);
        System.out.println("Is Stack Empty: " + stack.isEmpty());
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.displayStack();
        System.out.println("Popped Element: " + stack.pop());
        System.out.println("Popped Element: " + stack.pop());
        stack.displayStack();
        stack.push(6);
        System.out.println("Peeking Element: " + stack.peek());
        stack.displayStack();
        System.out.println("Is Stack Empty: " + stack.isEmpty());
        System.out.println("Stack Size: " + stack.getSize());
    }
}

OUTPUT:

Is Stack Empty: true
Inserting 1 into Stack.
Inserting 2 into Stack.
Inserting 3 into Stack.
Inserting 4 into Stack.
Stack overflow, ...cannot insert new element
Stack (top-->bottom): 4 3 2 1
Popping from Stack.
Popped Element: 4
Popping from Stack.
Popped Element: 3
Stack (top-->bottom): 2 1
Inserting 6 into Stack.
Popping from Stack.
Peeking Element: 6
Stack (top-->bottom): 6 2 1
Is Stack Empty: false
Stack Size: 3


                                            Implement Stack Using Linked List


Objective: Write an algorithm to implement Stack using Linked List.

If you do not know about then for starters its abstract data type in which follows the principle of LIFO (Last-In-First-Out) which means the data goes in last comes out

Approach:

Solution is quite simple, Earlier we have seen an article  “Linked List Implementation“, we need to make some changes to make it work as Stack.

Stack Operations:

Push() : Insert the element into linked list at the beginning and increase the size of the list. O(1) operation.

Pop() : Return the element first node from the linked list and move the head pointer to the second node. Decrease the size of the list. O(1) operation.

getSize(): Return the size of linked list.

displayStack(): Print the linked list.


PROGRAM:


public class StackUsingLinkedList {
    Node head= null;
    int size =0;

    public void push(int data){
        Node x = new Node(data);
        if(getSize()==0){
            head = x;
        }else{
            //add the Node at the start of a Linked List
            Node temp = head;
            x.next = temp;
            head = x;
        }
        System.out.println("Element "+ data + " is pushed into Stack");
        size++;
    }

    public int pop(){
        if(getSize()==0){
            System.out.println("Stack is Empty");
            return -1;
        }else{
            Node temp = head;
            head = head.next;
            size--;
            return temp.data;
        }

    }

    public void printStack(){
        Node curr = head;
        while(curr!=null){
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }
    public int getSize(){
        return size;
    }

    public static void main(String[] args) {
        StackUsingLinkedList stck = new StackUsingLinkedList();
        stck.push(1);
        stck.push(2);
        stck.push(4);
        stck.printStack();
        System.out.println("Pop out element " + stck.pop());
        stck.printStack();
    }
}
class Node{
    int data;
    Node next;
    public Node(int data){
        this.data = data;
    }
}


Output:

Element 1 is pushed into Stack
Element 2 is pushed into Stack
Element 4 is pushed into Stack
4 2 1
Pop out element 4
2 1

Binary Search Tree Points and Implementation need to complete before an Interview.

Binary Tree : A data structure in which we have nodes containing data and two references to other nodes, one on the left and one on the right.

Binary Tree consist of Nodes

• Nodes are nothing but objects of a class and each node has data and a link to the left node and right node.
• Usually we call the starting node of a tree as root.

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

•  Left and right node of a Leaf node points to NULL so you will know that you have reached to the end of the tree.

Binary Search Tree:

Often we call it as BST, is a type of Binary tree which has a special property.

Nodes smaller than root goes to the left of the root and Nodes greater than root goes to the right of the root.

Operations:

Insert(int n) : Add a node the tree with value n. Its O(lgn)

Find(int n) : Find a node the tree with value n. Its O(lgn)

Delete (int n) : Delete a node the tree with value n. Its O(lgn)

Display(): Prints the entire tree in increasing order. O(n).

Detail Explanations for the Operations:

Find(int n):

• Its very simple operation to perform.
• start from the root and compare root.data with n
• if root.data is greater than n that means we need to go to the left of the root.
• if root.data is smaller than n that means we need to go to the right of the root.
• if any point of time root.data is equal to the n then we have found the node, return true.
• if we reach to the leaves (end of the tree) return false, we didn’t find the element

Insert(int n):

• Very much similar to find() operation.
• To insert a node our first task is to find the place to insert the node.
• Take current = root .
• start from the current and compare root.data with n
• if current.data is greater than n that means we need to go to the left of the root.
• if current.data is smaller than n that means we need to go to the right of the root.
• if any point of time current is null that means we have reached to the leaf node, insert your node here with the help of parent node. (See code)

Delete(int n):

Complicated than Find() and Insert() operations. Here we have to deal with 3 cases.

• Node to be deleted is a leaf node ( No Children).
• Node to be deleted has only one child.
• Node to be deleted has two childrens.

Node to be deleted is a leaf node ( No Children).

its a very simple case, if a node to be deleted has no children then just traverse to that node, keep track of parent node and the side in which the node exist(left or right) and set parent.left = null or parent.right = null;

Node to be deleted has only one child.

1. its a slightly complex case. if a node to be deleted(deleteNode) has only one child then just traverse to that node, keep track of parent node and the side in which the node exist(left or right).
2. check which side child is null (since it has only one child).
3. Say node to be deleted has child on its left side . Then take the entire sub tree from the left side and add it to the parent and the side on which deleteNode exist, see step 1 and example.

Node to be deleted has two children.

Now this is quite exciting 

You just cannot replace the deleteNode with any of its child, Why? Lets try out a example.

What to do now?????

Dont worry we have solution for this 

Find The Successor:

Successor is the node which will replace the deleted node. Now the question is to how to find it and where to find it.

Successor is the smaller node in the right sub tree of the node to be deleted.

Display() : To know about how we are displaying nodes in increasing order, Click Here

Complete Example :

Complete Example Code:

	public class BinarySearchTree {
	public static Node root;
	public BinarySearchTree(){
	this.root = null;
	}
	public boolean find(int id){
	Node current = root;
	while(current!=null){
	if(current.data==id){
	return true;
	}else if(current.data>id){
	current = current.left;
	}else{
	current = current.right;
	}
	}
	return false;
	}
	public boolean delete(int id){
	Node parent = root;
	Node current = root;
	boolean isLeftChild = false;
	while(current.data!=id){
	parent = current;
	if(current.data>id){
	isLeftChild = true;
	current = current.left;
	}else{
	isLeftChild = false;
	current = current.right;
	}
	if(current ==null){
	return false;
	}
	}
	//if i am here that means we have found the node
	//Case 1: if node to be deleted has no children
	if(current.left==null && current.right==null){
	if(current==root){
	root = null;
	}
	if(isLeftChild ==true){
	parent.left = null;
	}else{
	parent.right = null;
	}
	}
	//Case 2 : if node to be deleted has only one child
	else if(current.right==null){
	if(current==root){
	root = current.left;
	}else if(isLeftChild){
	parent.left = current.left;
	}else{
	parent.right = current.left;
	}
	}
	else if(current.left==null){
	if(current==root){
	root = current.right;
	}else if(isLeftChild){
	parent.left = current.right;
	}else{
	parent.right = current.right;
	}
	}else if(current.left!=null && current.right!=null){
	//now we have found the minimum element in the right sub tree
	Node successor = getSuccessor(current);
	if(current==root){
	root = successor;
	}else if(isLeftChild){
	parent.left = successor;
	}else{
	parent.right = successor;
	}
	successor.left = current.left;
	}
	return true;
	}
	public Node getSuccessor(Node deleleNode){
	Node successsor =null;
	Node successsorParent =null;
	Node current = deleleNode.right;
	while(current!=null){
	successsorParent = successsor;
	successsor = current;
	current = current.left;
	}
	//check if successor has the right child, it cannot have left child for sure
	// if it does have the right child, add it to the left of successorParent.
	// successsorParent
	if(successsor!=deleleNode.right){
	successsorParent.left = successsor.right;
	successsor.right = deleleNode.right;
	}
	return successsor;
	}
	public void insert(int id){
	Node newNode = new Node(id);
	if(root==null){
	root = newNode;
	return;
	}
	Node current = root;
	Node parent = null;
	while(true){
	parent = current;
	if(id<current.data){
	current = current.left;
	if(current==null){
	parent.left = newNode;
	return;
	}
	}else{
	current = current.right;
	if(current==null){
	parent.right = newNode;
	return;
	}
	}
	}
	}
	public void display(Node root){
	if(root!=null){
	display(root.left);
	System.out.print(" " + root.data);
	display(root.right);
	}
	}
	public static void main(String arg[]){
	BinarySearchTree b = new BinarySearchTree();
	b.insert(3);b.insert(8);
	b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);
	b.insert(20);b.insert(25);b.insert(15);b.insert(16);
	System.out.println("Original Tree : ");
	b.display(b.root);
	System.out.println("");
	System.out.println("Check whether Node with value 4 exists : " + b.find(4));
	System.out.println("Delete Node with no children (2) : " + b.delete(2));
	b.display(root);
	System.out.println("\n Delete Node with one child (4) : " + b.delete(4));
	b.display(root);
	System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));
	b.display(root);
	}
	}
	class Node{
	int data;
	Node left;
	Node right;
	public Node(int data){
	this.data = data;
	left = null;
	right = null;
	}
	}

view rawBinarySearchTree.java hosted with  by GitHub

Output:
Original Tree :
1 2 3 4 6 8 9 10 15 16 20 25
Check whether Node with value 4 exists : true
Delete Node with no children (2) : true
1 3 4 6 8 9 10 15 16 20 25
Delete Node with one child (4) : true
1 3 6 8 9 10 15 16 20 25
Delete Node with Two children (10) : true
1 3 6 8 9 15 16 20 25

Implementation of Binary search tree using Java

BST.java


import java.util.NoSuchElementException;

/**
 *  The {@code BST} class represents an ordered symbol table of generic
 *  key-value pairs.
 *  It supports the usual <em>put</em>, <em>get</em>, <em>contains</em>,
 *  <em>delete</em>, <em>size</em>, and <em>is-empty</em> methods.
 *  It also provides ordered methods for finding the <em>minimum</em>,
 *  <em>maximum</em>, <em>floor</em>, <em>select</em>, <em>ceiling</em>.
 *  It also provides a <em>keys</em> method for iterating over all of the keys.
 *  A symbol table implements the <em>associative array</em> abstraction:
 *  when associating a value with a key that is already in the symbol table,
 *  the convention is to replace the old value with the new value.
 *  Unlike {@link java.util.Map}, this class uses the convention that
 *  values cannot be {@code null}—setting the
 *  value associated with a key to {@code null} is equivalent to deleting the key
 *  from the symbol table.
 *  <p>
 *  This implementation uses an (unbalanced) binary search tree. It requires that
 *  the key type implements the {@code Comparable} interface and calls the
 *  {@code compareTo()} and method to compare two keys. It does not call either
 *  {@code equals()} or {@code hashCode()}.
 *  The <em>put</em>, <em>contains</em>, <em>remove</em>, <em>minimum</em>,
 *  <em>maximum</em>, <em>ceiling</em>, <em>floor</em>, <em>select</em>, and
 *  <em>rank</em>  operations each take
 *  linear time in the worst case, if the tree becomes unbalanced.
 *  The <em>size</em>, and <em>is-empty</em> operations take constant time.
 *  Construction takes constant time.
 *  <p>
 *  For other implementations, see {@link ST}, {@link BinarySearchST},
 *  {@link SequentialSearchST}, {@link RedBlackBST},
 *  {@link SeparateChainingHashST}, and {@link LinearProbingHashST},
 *
 *  @author Nishant Sharma
 */

 public class BST<Key extends Comparable<Key>, Value> {
    private Node root;             // root of BST

    private class Node {
        private Key key;           // sorted by key
        private Value val;         // associated data
        private Node left, right;  // left and right subtrees
        private int size;          // number of nodes in subtree

        public Node(Key key, Value val, int size) {
            this.key = key;
            this.val = val;
            this.size = size;
        }
    }

    /**
     * Initializes an empty symbol table.
     */
    public BST() {
    }

    /**
     * Returns true if this symbol table is empty.
     * @return {@code true} if this symbol table is empty; {@code false} otherwise
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * Returns the number of key-value pairs in this symbol table.
     * @return the number of key-value pairs in this symbol table
     */
    public int size() {
        return size(root);
    }

    // return number of key-value pairs in BST rooted at x
    private int size(Node x) {
        if (x == null) return 0;
        else return x.size;
    }

    /**
     * Does this symbol table contain the given key?
     *
     * @param  key the key
     * @return {@code true} if this symbol table contains {@code key} and
     *         {@code false} otherwise
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public boolean contains(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to contains() is null");
        return get(key) != null;
    }

    /**
     * Returns the value associated with the given key.
     *
     * @param  key the key
     * @return the value associated with the given key if the key is in the symbol table
     *         and {@code null} if the key is not in the symbol table
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        if (key == null) throw new IllegalArgumentException("calls get() with a null key");
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) return get(x.left, key);
        else if (cmp > 0) return get(x.right, key);
        else              return x.val;
    }

    /**
     * Inserts the specified key-value pair into the symbol table, overwriting the old 
     * value with the new value if the symbol table already contains the specified key.
     * Deletes the specified key (and its associated value) from this symbol table
     * if the specified value is {@code null}.
     *
     * @param  key the key
     * @param  val the value
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public void put(Key key, Value val) {
        if (key == null) throw new IllegalArgumentException("calls put() with a null key");
        if (val == null) {
            delete(key);
            return;
        }
        root = put(root, key, val);
        assert check();
    }

    private Node put(Node x, Key key, Value val) {
        if (x == null) return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x.left  = put(x.left,  key, val);
        else if (cmp > 0) x.right = put(x.right, key, val);
        else              x.val   = val;
        x.size = 1 + size(x.left) + size(x.right);
        return x;
    }


    /**
     * Removes the smallest key and associated value from the symbol table.
     *
     * @throws NoSuchElementException if the symbol table is empty
     */
    public void deleteMin() {
        if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
        root = deleteMin(root);
        assert check();
    }

    private Node deleteMin(Node x) {
        if (x.left == null) return x.right;
        x.left = deleteMin(x.left);
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

    /**
     * Removes the largest key and associated value from the symbol table.
     *
     * @throws NoSuchElementException if the symbol table is empty
     */
    public void deleteMax() {
        if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
        root = deleteMax(root);
        assert check();
    }

    private Node deleteMax(Node x) {
        if (x.right == null) return x.left;
        x.right = deleteMax(x.right);
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

    /**
     * Removes the specified key and its associated value from this symbol table     
     * (if the key is in this symbol table).    
     *
     * @param  key the key
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("calls delete() with a null key");
        root = delete(root, key);
        assert check();
    }

    private Node delete(Node x, Key key) {
        if (x == null) return null;

        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x.left  = delete(x.left,  key);
        else if (cmp > 0) x.right = delete(x.right, key);
        else { 
            if (x.right == null) return x.left;
            if (x.left  == null) return x.right;
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        } 
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    } 


    /**
     * Returns the smallest key in the symbol table.
     *
     * @return the smallest key in the symbol table
     * @throws NoSuchElementException if the symbol table is empty
     */
    public Key min() {
        if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table");
        return min(root).key;
    } 

    private Node min(Node x) { 
        if (x.left == null) return x; 
        else                return min(x.left); 
    } 

    /**
     * Returns the largest key in the symbol table.
     *
     * @return the largest key in the symbol table
     * @throws NoSuchElementException if the symbol table is empty
     */
    public Key max() {
        if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table");
        return max(root).key;
    } 

    private Node max(Node x) {
        if (x.right == null) return x; 
        else                 return max(x.right); 
    } 

    /**
     * Returns the largest key in the symbol table less than or equal to {@code key}.
     *
     * @param  key the key
     * @return the largest key in the symbol table less than or equal to {@code key}
     * @throws NoSuchElementException if there is no such key
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public Key floor(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to floor() is null");
        if (isEmpty()) throw new NoSuchElementException("calls floor() with empty symbol table");
        Node x = floor(root, key);
        if (x == null) return null;
        else return x.key;
    } 

    private Node floor(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp == 0) return x;
        if (cmp <  0) return floor(x.left, key);
        Node t = floor(x.right, key); 
        if (t != null) return t;
        else return x; 
    } 

    public Key floor2(Key key) {
        return floor2(root, key, null);
    }

    private Key floor2(Node x, Key key, Key best) {
        if (x == null) return best;
        int cmp = key.compareTo(x.key);
        if      (cmp  < 0) return floor2(x.left, key, best);
        else if (cmp  > 0) return floor2(x.right, key, x.key);
        else               return x.key;
    } 

    /**
     * Returns the smallest key in the symbol table greater than or equal to {@code key}.
     *
     * @param  key the key
     * @return the smallest key in the symbol table greater than or equal to {@code key}
     * @throws NoSuchElementException if there is no such key
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public Key ceiling(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to ceiling() is null");
        if (isEmpty()) throw new NoSuchElementException("calls ceiling() with empty symbol table");
        Node x = ceiling(root, key);
        if (x == null) return null;
        else return x.key;
    }

    private Node ceiling(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp == 0) return x;
        if (cmp < 0) { 
            Node t = ceiling(x.left, key); 
            if (t != null) return t;
            else return x; 
        } 
        return ceiling(x.right, key); 
    } 

    /**
     * Return the key in the symbol table whose rank is {@code k}.
     * This is the (k+1)st smallest key in the symbol table.
     *
     * @param  k the order statistic
     * @return the key in the symbol table of rank {@code k}
     * @throws IllegalArgumentException unless {@code k} is between 0 and
     *        <em>n</em>–1
     */
    public Key select(int k) {
        if (k < 0 || k >= size()) {
            throw new IllegalArgumentException("argument to select() is invalid: " + k);
        }
        Node x = select(root, k);
        return x.key;
    }

    // Return key of rank k. 
    private Node select(Node x, int k) {
        if (x == null) return null; 
        int t = size(x.left); 
        if      (t > k) return select(x.left,  k); 
        else if (t < k) return select(x.right, k-t-1); 
        else            return x; 
    } 

    /**
     * Return the number of keys in the symbol table strictly less than {@code key}.
     *
     * @param  key the key
     * @return the number of keys in the symbol table strictly less than {@code key}
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public int rank(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to rank() is null");
        return rank(key, root);
    } 

    // Number of keys in the subtree less than key.
    private int rank(Key key, Node x) {
        if (x == null) return 0; 
        int cmp = key.compareTo(x.key); 
        if      (cmp < 0) return rank(key, x.left); 
        else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right); 
        else              return size(x.left); 
    } 

    /**
     * Returns all keys in the symbol table as an {@code Iterable}.
     * To iterate over all of the keys in the symbol table named {@code st},
     * use the foreach notation: {@code for (Key key : st.keys())}.
     *
     * @return all keys in the symbol table
     */
    public Iterable<Key> keys() {
        if (isEmpty()) return new Queue<Key>();
        return keys(min(), max());
    }

    /**
     * Returns all keys in the symbol table in the given range,
     * as an {@code Iterable}.
     *
     * @param  lo minimum endpoint
     * @param  hi maximum endpoint
     * @return all keys in the symbol table between {@code lo} 
     *         (inclusive) and {@code hi} (inclusive)
     * @throws IllegalArgumentException if either {@code lo} or {@code hi}
     *         is {@code null}
     */
    public Iterable<Key> keys(Key lo, Key hi) {
        if (lo == null) throw new IllegalArgumentException("first argument to keys() is null");
        if (hi == null) throw new IllegalArgumentException("second argument to keys() is null");

        Queue<Key> queue = new Queue<Key>();
        keys(root, queue, lo, hi);
        return queue;
    } 

    private void keys(Node x, Queue<Key> queue, Key lo, Key hi) { 
        if (x == null) return; 
        int cmplo = lo.compareTo(x.key); 
        int cmphi = hi.compareTo(x.key); 
        if (cmplo < 0) keys(x.left, queue, lo, hi); 
        if (cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key); 
        if (cmphi > 0) keys(x.right, queue, lo, hi); 
    } 

    /**
     * Returns the number of keys in the symbol table in the given range.
     *
     * @param  lo minimum endpoint
     * @param  hi maximum endpoint
     * @return the number of keys in the symbol table between {@code lo} 
     *         (inclusive) and {@code hi} (inclusive)
     * @throws IllegalArgumentException if either {@code lo} or {@code hi}
     *         is {@code null}
     */
    public int size(Key lo, Key hi) {
        if (lo == null) throw new IllegalArgumentException("first argument to size() is null");
        if (hi == null) throw new IllegalArgumentException("second argument to size() is null");

        if (lo.compareTo(hi) > 0) return 0;
        if (contains(hi)) return rank(hi) - rank(lo) + 1;
        else              return rank(hi) - rank(lo);
    }

    /**
     * Returns the height of the BST (for debugging).
     *
     * @return the height of the BST (a 1-node tree has height 0)
     */
    public int height() {
        return height(root);
    }
    private int height(Node x) {
        if (x == null) return -1;
        return 1 + Math.max(height(x.left), height(x.right));
    }

    /**
     * Returns the keys in the BST in level order (for debugging).
     *
     * @return the keys in the BST in level order traversal
     */
    public Iterable<Key> levelOrder() {
        Queue<Key> keys = new Queue<Key>();
        Queue<Node> queue = new Queue<Node>();
        queue.enqueue(root);
        while (!queue.isEmpty()) {
            Node x = queue.dequeue();
            if (x == null) continue;
            keys.enqueue(x.key);
            queue.enqueue(x.left);
            queue.enqueue(x.right);
        }
        return keys;
    }

  /*************************************************************************
    *  Check integrity of BST data structure.
    ***************************************************************************/
    private boolean check() {
        if (!isBST())            StdOut.println("Not in symmetric order");
        if (!isSizeConsistent()) StdOut.println("Subtree counts not consistent");
        if (!isRankConsistent()) StdOut.println("Ranks not consistent");
        return isBST() && isSizeConsistent() && isRankConsistent();
    }

    // does this binary tree satisfy symmetric order?
    // Note: this test also ensures that data structure is a binary tree since order is strict
    private boolean isBST() {
        return isBST(root, null, null);
    }

    // is the tree rooted at x a BST with all keys strictly between min and max
    // (if min or max is null, treat as empty constraint)
    // Credit: Bob Dondero's elegant solution
    private boolean isBST(Node x, Key min, Key max) {
        if (x == null) return true;
        if (min != null && x.key.compareTo(min) <= 0) return false;
        if (max != null && x.key.compareTo(max) >= 0) return false;
        return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
    } 

    // are the size fields correct?
    private boolean isSizeConsistent() { return isSizeConsistent(root); }
    private boolean isSizeConsistent(Node x) {
        if (x == null) return true;
        if (x.size != size(x.left) + size(x.right) + 1) return false;
        return isSizeConsistent(x.left) && isSizeConsistent(x.right);
    } 

    // check that ranks are consistent
    private boolean isRankConsistent() {
        for (int i = 0; i < size(); i++)
            if (i != rank(select(i))) return false;
        for (Key key : keys())
            if (key.compareTo(select(rank(key))) != 0) return false;
        return true;
    }


    /**
     * Unit tests the {@code BST} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) { 
        BST<String, Integer> st = new BST<String, Integer>();
        for (int i = 0; !StdIn.isEmpty(); i++) {
            String key = StdIn.readString();
            if ((st.size() > 1) && (st.floor(key) != st.floor2(key)))
                throw new RuntimeException("floor() function inconsistent");
            st.put(key, i);
        }

        for (String s : st.levelOrder())
            StdOut.println(s + " " + st.get(s));

        StdOut.println();

        for (String s : st.keys())
            StdOut.println(s + " " + st.get(s));
    }
}