BST

bst.java

import java.io.*;
import java.util.*;


class Solution {
  public static void main(String... args){
    System.out.println("Coding a Binary Search Tree"); 
    
    int[] original = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 
                      101, 79, 94, 90, 97};
    
    int[] input = null;
    
    System.out.println("original: " + Arrays.toString(original));
    
    input = original.clone();
    
    BinarySearchTree bst = new BinarySearchTree();
    
    for(int i : input){
      bst.add(i);
    }
    
    System.out.println("inOrderTraverse");
    bst.inOrderTraverse(bst.root);
    
    System.out.println("preOrderTraverse");
    bst.preOrderTraverse(bst.root);
    
    System.out.println("postOrderTraverse");
    bst.postOrderTraverse(bst.root);
    
    System.out.println("Contains 113: " + bst.queryRecursive(bst.root, 113));
    System.out.println("Contains 1132: " + bst.queryRecursive(bst.root, 1132));
    System.out.println("Contains 113: " + bst.queryIterative(bst.root, 113));
    System.out.println("Contains 1132: " + bst.queryIterative(bst.root, 1132));
    
    System.out.println("Max: " + bst.max(bst.root));
    System.out.println("Min: " + bst.min(bst.root));
  }
}

class BinarySearchTree{
  Node root;
  
  // TODO delete
  
  public int max(Node node){
    if(node == null){
      throw new RuntimeException();
    }
    
    while(node.rightChild != null){
      node = node.rightChild;
    }
    
    return node.value;
  }
  
  public int min(Node node){
    if(node == null){
      throw new RuntimeException();
    }
    
    while(node.leftChild != null){
      node = node.leftChild;
    }
    
    return node.value;
  }
  
  public boolean queryRecursive(Node node, int value){
    if(node == null){
      return false;
    }
    if(node.value == value){
      return true;
    }
    
    if(value >= node.value){
      return queryRecursive(node.rightChild, value);
    }else{
      return queryRecursive(node.leftChild, value);
    }
  }
  
  public boolean queryIterative(Node node, int value){
    while(node != null){
      if(node.value == value){
        return true;
      }
      if(value >= node.value){
        node = node.rightChild;
      }else{
        node = node.leftChild;
      }
    }
  
    return false;
  }
  
  public void add(int value){
    Node newNode = new Node(value);
    
    if(root == null){
      root = newNode;
      return;
    }
    
    Node focus = root;
    
    while(true){
      if(newNode.value >= focus.value){
        if(focus.rightChild == null){
          focus.rightChild = newNode;
          return;
        }
        focus = focus.rightChild;
      }else{
        if(focus.leftChild == null){
          focus.leftChild = newNode;
          return;
        }
        focus = focus.leftChild;
      }
    }
  }
  
  public void inOrderTraverse(Node node){
    if(node == null){
      return;
    }
    
    inOrderTraverse(node.leftChild);
    System.out.println(node.value);
    inOrderTraverse(node.rightChild);
  }
  
  public void preOrderTraverse(Node node){
    if(node == null){
      return;
    }
    
    System.out.println(node.value);
    preOrderTraverse(node.leftChild);
    preOrderTraverse(node.rightChild);
  }
  
  public void postOrderTraverse(Node node){
    if(node == null){
      return;
    }
    
    preOrderTraverse(node.leftChild);
    preOrderTraverse(node.rightChild);
    System.out.println(node.value);
  }
  
}

class Node{
  Node(int value){
    this.value = value;
  }
  
  int value;
  Node leftChild, rightChild;
}