// Binary Search Tree class
// Xiwei Wang
import java.util.*;

public class BST {
    // instance variables
    private BSTNode m_root;
    private int m_size;

    // constructor
    public BST() {
        m_root = null;
        m_size = 0;
    }

    // This method returns the number of elements in the tree.
    // Do not make any changes to this method!
    public int size() {
        return m_size;
    }

    // This method clears the content of the tree.
    // Do not make any changes to this method!
    public void clear() {
        m_root = null;
        m_size = 0;
    }

    // This non-recursive method takes a string and inserts it into the binary
    // search tree, keeping the tree ordered.
    public void add(String value) {
        BSTNode to_add = new BSTNode(value);
        if (m_root == null) {
            m_root = to_add;
            m_size++;
        }
        else {
            BSTNode current = m_root;
            BSTNode parent = null;
            int comparison = 0;
            while (current != null) {
                comparison = value.compareTo(current.getInfo());
                if (comparison > 0) {
                    parent = current;
                    current = current.getRight();
                }
                else if (comparison < 0) {
                    parent = current;
                    current = current.getLeft();
                }
                else
                    return;
            }
            if (comparison > 0)
                parent.setRight(to_add);
            else
                parent.setLeft(to_add);
            m_size++;
        }
    }

    // This non-recursive method returns a string that represents the in-order traversal
    // of the binary search tree.
    public String inOrder() {
        String return_string = "";
        Stack<BSTNode> stack = new Stack<BSTNode>();
        BSTNode current = m_root;
        while ((current != null) || (stack.size() > 0)) {
            while (current != null) {
                stack.push(current);
                current = current.getLeft();
            }
            current = stack.pop();
            return_string += current.getInfo() + " ";
            current = current.getRight();
        }
        return return_string;
    }

    // This method returns the smallest element in the binary search tree. You
    // are not allowed to create any additional structures, including but not
    // limited to arrays, stacks, queues, or other trees.
    public String min() {
        BSTNode current = m_root;
        while (current.getLeft() != null)
            current = current.getLeft();
        return current.getInfo();
    }

    // This method takes a reference to the root of the expression, evaluates
    // the tree, and returns the result as an int.
    public int evaluate(BSTNode node) {
        String value = node.getInfo();
        switch (value) {
            case "+":
                return evaluate(node.getLeft()) + evaluate(node.getRight());

            case "-":
                return evaluate(node.getLeft()) - evaluate(node.getRight());

            case "*":
                return evaluate(node.getLeft()) * evaluate(node.getRight());

            case "/":
                return evaluate(node.getLeft()) / evaluate(node.getRight());

            default:
                return Integer.parseInt(node.getInfo());
        }

    }
}