Coursera - Data structures: Measuring and Optimizing Performance - Week 4

BinaryTree.java

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<E extends Comparable<E>> {
  TreeNode<E> root;
  
  public BinaryTree() {
    root = null;
  }
 
  private void preOrder(TreeNode<E> node) {
    if(node != null) {
      node.visit();
      preOrder(node.getLeft());
      preOrder(node.getRight());
    }
  }
  
  public void preOrder() {
    this.preOrder(root);
  }
  
  private void postOrder(TreeNode<E> node) {
    if(node != null) {
      postOrder(node.getLeft());
      postOrder(node.getRight());
      node.visit();
    }
  }
  
  public void postOrder() {
    this.postOrder(root);
  }
  
  private void inOrder(TreeNode<E> node) {
    if(node != null) {
      inOrder(node.getLeft());
      node.visit();
      inOrder(node.getRight());
    }
  }
  
  public void inOrder() {
    this.inOrder(root);
  }
  
  public void levelOrder() {
    Queue<TreeNode<E>> q = new LinkedList<TreeNode<E>>();
    q.add(root);
    while(!q.isEmpty()) {
      TreeNode<E> curr = q.remove();
      if(curr != null) {
        curr.visit();
        q.add(curr.getLeft());
        q.add(curr.getRight());
      }
    }
  }
  
  public boolean contains(E toFind) {
    TreeNode<E> curr = root;
    while(curr != null) {
      int comp = toFind.compareTo(curr.getData());
      if(comp < 0) {
        curr = curr.getLeft();
      } else if(comp > 0) {
        curr = curr.getRight();
      } else {
        return true;
      }
    }
    return false;
  }

  public boolean insert(E toInsert) {
    TreeNode<E> curr = root;
    int comp = toInsert.compareTo(curr.getData());
    while(comp < 0 && curr.getLeft() != null || comp > 0 && curr.getRight() != null) {
      if(comp < 0) {
        curr = curr.getLeft();
      } else {
        curr = curr.getRight();
      }
      comp = toInsert.compareTo(curr.getData());
    }
    // curr points to the last node
    if(comp < 0) {
      curr.setLeft(toInsert, curr);
    } else if(comp > 0) {
      curr.setRight(toInsert, curr);
    } else {
      return false; // we found the element
    }
    return true;
  }
  
}

TreeNode.java

public class TreeNode<E extends Comparable<E>> {
  private E value;
  private TreeNode<E> parent;
  private TreeNode<E> left;
  private TreeNode<E> right;
  
  public TreeNode(E newValue) {
    this.value = newValue;
    this.parent = null;
    this.left = null;
    this.right = null;
  }
  
  public TreeNode(E val, TreeNode<E> par) {
    this.value = val;
    this.parent = par;
    this.left = null;
    this.right = null;
  }
  
  public E getData() {
    return value;
  }
  
  public TreeNode<E> addLeftChild(E val) {
    this.left = new TreeNode<E>(val, this);
    return this.left;
  }
  
  public TreeNode<E> getLeft() {
    return left;
  }
  
  public void setLeft(E value, TreeNode<E> node) {
    TreeNode<E> newLeft = new TreeNode<E>(value, node);
    this.left = newLeft;
  }
  
  public TreeNode<E> getRight() {
    return right;
  }
  
  public void setRight(E value, TreeNode<E> node) {
    TreeNode<E> newRight = new TreeNode<E>(value, node);
    this.right = newRight;
  }
  
  public void visit() {
    System.out.print(value);
  }
    
  public int compareTo(TreeNode<E> otherTreeNode) {
    return this.getData().compareTo(otherTreeNode.getData());
  }
  
}