TrinaryTree

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

public class TrinaryTree {
  private TrinaryNode root;

  public TrinaryTree insert(int []ary) {
    for (int i: ary) {
      insert(i);
    }
    return this;
  }

  public TrinaryTree insert(int x) {
    TrinaryNode node = new TrinaryNode(x);
    if (root == null) {
      root = node;
    } else {
      TrinaryNode cur = root;
      while (cur != null) {
        // compare new node and current node
        if (x < cur.val) {
          if (cur.left == null) {
            cur.left = node;
            break;
          } else {
            cur = cur.left;
          }
        } else if (x == cur.val) {
          node.mid = cur.mid;
          cur.mid = node;
          break;
        } else /* if (x > cur.val) */ {
          if (cur.right == null) {
            cur.right = node;
            break;
          } else {
            cur = cur.right;
          }
        }
      }
    }
    return this;
  }

  public TrinaryTree delete(int x) {
    if (root != null) {
      // find the node to delete
      TrinaryNode curParent = null;
      TrinaryNode cur = root;
      while (cur != null && cur.val != x) {
        curParent = cur;
        if (x < cur.val){
          cur = cur.left;
        } else /* if (x > cur.val) */ {
          cur = cur.right;
        }
      }

      if (cur != null) {
        // found cur.val == x, cur is the node to be deleted, curParent is cur's parent
        if (cur.mid != null) {
          // if cur has mid child, remove one mid
          cur.mid = cur.mid.mid;
        } else if (cur.left == null || cur.right == null) {
          // if one of them is null, find the non-null one and splice it
          // amazingly leave node case could use the same code
          TrinaryNode child = (cur.left != null) ? cur.left : cur.right;
          if (curParent == null) {
            root = child;
          } else {
            if (cur.val < curParent.val) {
              curParent.left = child;
            } else {
              curParent.right = child;
            }
          }
        } else /* if (cur.left != null && cur.right != null) */ {
          // if cur doesn't have mid child && has both left/right child
          // find successor of cur
          TrinaryNode successor = cur.right;
          TrinaryNode successorParent = null;
          while (successor.left != null) {
            successorParent = successor;
            successor = successor. left;
          }
          cur.val = successor.val;  // overwrite value of the node to be deleted by successor
          if (successorParent != null) {
            successorParent.left = successor.right;
          } else {
            cur.right = successor.right;
          }
        }
      }
    }
    return this;
  }

  public TrinaryNode getRootNode() {
    return root;
  }
}

class TrinaryNode {
  TrinaryNode left;
  TrinaryNode mid;
  TrinaryNode right;
  int val;

  public TrinaryNode(int val) {
    this.val = val;
  }

  @Override
  public String toString() {
    return "" + val;
  }

  // BFS representation
  public String serialize() {
    Queue <TrinaryNode> q = new LinkedList<TrinaryNode>();
    StringBuilder sb = new StringBuilder();
    q.add(this);

    while (!q.isEmpty()) {
      TrinaryNode node = q.remove();
      if (node == null) {
        sb.append("# ");
      } else {
        sb.append(node.val + " ");
        if (node.left != null || node.mid != null || node.right != null) {
          q.add(node.left);
          q.add(node.mid);
          q.add(node.right);
        }
      }
    }
    return sb.toString();
  }
}