/*
   TreeNotes.txt
   CIS 250
   Dave Klick

   Pseudocode for a binary tree class.
*/

class Tree<T>:
   // define what each node is
   class Node
      T data
      Node left, right
      Node(T val): set data to val passed in
      getData(): return data
      display(): display data
      compareTo(Node n): return comparison of data to n.data
      toString(): could be a variety of output formats

   // instance variables for tree
   Node root = null
   DUPS_ALLOWED = true
   Tree(): nothing needs to be done here
   Tree(boolean flag) DUPS_ALLOWED = flag

   // search routine
   T find(T val)
      Node cur = root
      while cur is not null
         compare val to cur.data
         <: cur = cur.left
         >: cur = cur.right
         =: return cur.data
      return null  // not found

   // insert value into tree
   boolean insert(T val)
      Node parent, cur
      Node n = Node(val)
      if root is null then root = n  // only item in tree
      otherwise
         cur = root
         loop forever
            parent = cur
            compare val to cur.data
            <: cur = cur.left
               if cur is null then parent.left = n and return true
            >: cur = cur.right
               if cur is null then parent.right = n and return true
            =: if duplicates allowed then
                  cur = cur.right
                  if cur is null then parent.right = n and return true
               otherwise
                  return false
      return false   // should never get here

   traverse(): if root isn't null then traverse(root)

   traverse(Node node)
      if node.left isn't null then traverse(node.left)
      display node
      if node.right isn't null then traverse(node.right)

   public boolean delete(T val) {
      Node current = root, parent = root
      leftChild = true

      // search for node to delete
      while current.data != val
         parent = current
         if val < current.data then
            current = current.left
            leftChild = true
         otherwise
            current = current.right
            leftChild = false
         // if value not found, return false
         if current is null then return false

      // if we got here, then
      //    1. current refers to node to be deleted
      //    2. parent refers to its parent
      //    3. leftChild indicates current:parent relation

      // check for delete with no children
      if current's left and right are both null then
         if current == root then root = null
         otherwise if leftChild then parent.left = null
         otherwise parent.right = null

      // check for delete with one child - left
      otherwise if current.right is null then
         if current == root then root = current.left
         otherwise if leftChild then parent.left = current.left
         otherwise parent.right = current.left

      // check for delete with one child - right
      otherwise if current.left is null then
         if current == root then root = current.right
         otherwise if leftChild then parent.left = current.right
         otherwise parent.right = current.right

      // must be delete with two children
      otherwise

         // get successor of node to be deleted
         Nodes delNode = successor = successorParent = current

         // succesor is in right subtree ...
         Node tmp = delNode.right

         // ... and then left as far as possible
         // (smallest element in right subtree)
         while tmp is not null
            successorParent = successor
            successor = tmp
            tmp = tmp.left

         // do this part only if successor isn't right
         //    child of node to be deleted
         if successor != delNode.right then
            // attach successor's child to it's parent
            successorParent.left = successor.right
            // make right subtree successor's right child
            successor.right = delNode.right

         // make deleted node's parent point to successor
         if current is root then root = successor
         otherwise if leftChild then parent.left = successor
         otherwise parent.right = successor

         // make left subtree successor's left child
         successor.left = current.left

      return true;