import static org.junit.Assert.*;
import org.junit.Test;

// Markierter Binaerbaum
public class BinTree {
  private TreeNode root;

  // Berechnet die Summe der Markierungen des Baums
  public int sum() {
    return sum(this.root);
  }
  private int sum(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return node.getMark() + sum(node.getLeft())
                          + sum(node.getRight());
  }

  // Testet, ob es einen Knoten mt Markierung x in dem Baum gibt
  public boolean contains(int x) {
    return contains(x, this.root);
  }
  private boolean contains(int x, TreeNode n){
    if (n == null) {
      return false;
    } else {
      return n.getMark() == x
        || contains(x, n.getLeft())
        || contains(x, n.getRight());
    }
  }

  // Fuegt einen Knoten mit Markierung element in den Baum ein
  // (Die Methode erhält die Suchbaumeigenschaft, dies ist hier allerdings nicht notwendig!)
  public void add(int element) {
    this.root = add(this.root, element);
  }

  private TreeNode add(TreeNode node, int element){
    if (node == null) {
        return new TreeNode(element,null,null);
    } else if (element <= node.getMark()) {
        node.setLeft(add(node.getLeft(), element));
    } else {
        node.setRight(add(node.getRight(), element));
    }
    return node;
  }

  @Test
  public void test() {
    BinTree t = new BinTree();
    t.add(4);
    t.add(9);
    t.add(2);
    assertEquals(true, t.contains(4));
    assertEquals(false, t.contains(3));
    assertEquals(15, t.sum());
  }

}