import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BinaryTree {
  private Node root;

  public void insert(int value) {

    Node node = new Node(value);

    if (root == null) {
      root = node;
      return;
    }

    insertNode(root, node);
  }

  private void insertNode(Node node, Node nodeToInsert) {
    if (node.getValue() > nodeToInsert.getValue()) {
      if (node.getLeft() == null) {
        node.setLeft(nodeToInsert);
      } else {
        insertNode(node.getLeft(), nodeToInsert);
      }
    }

    if (node.getValue() < nodeToInsert.getValue()) {
      if (node.getRight() == null) {
        node.setRight(nodeToInsert);
      } else {
        insertNode(node.getRight(), nodeToInsert);
      }
    }
  }

  public Node getRoot() {
    return root;
  }

  public Node find(int value) {
    Node node = root;

    boolean found = false;

    while (!found && node != null) {
      if (node.getValue() == value) {
        found = true;
      }

      if (node.getValue() > value) {
        node = node.getLeft();
      }

      if (node.getValue() < value)
        node = node.getRight();
    }

    return node;
  }

  public int findMin() {
    Node node = root;

    if (node == null) {
      return 0;
    }

    while (node.getLeft() != null) {
      node = node.getLeft();
    }

    return node.getValue();
  }

  public int findMax() {
    Node node = root;

    if (node == null) {
      return 0;
    }

    while (node.getRight() != null) {
      node = node.getRight();
    }

    return node.getValue();
  }

  public List<Node> traverseInOrder() {
    List<Node> visitedNodes = new ArrayList<Node>();

    traverseInOrder(root, visitedNodes);

    return visitedNodes;
  }

  public List<Node> traversePreOrder() {
    List<Node> visitedNodes = new ArrayList<Node>();

    traversePreOrder(root, visitedNodes);

    return visitedNodes;
  }

  public List<Node> traverPostOrder() {
    List<Node> visitedNodes = new ArrayList<Node>();

    traversePostOrder(root, visitedNodes);

    return visitedNodes;
  }

  private void traversePostOrder(Node node, List<Node> visited) {
    if (node == null) {
      return;
    }
    traverseInOrder(node.getLeft(), visited);
    traverseInOrder(node.getRight(), visited);
    visited.add(node);
  }

  private void traversePreOrder(Node node, List<Node> visited) {
    if (node == null) {
      return;
    }

    traverseInOrder(node.getLeft(), visited);
    visited.add(node);
    traverseInOrder(node.getRight(), visited);

  }

  public void traverseInOrder(Node node, List<Node> visited) {
    if (node == null) {
      return;
    }

    visited.add(node);
    traverseInOrder(node.getLeft(), visited);
    traverseInOrder(node.getRight(), visited);

  }
}