package kata;

import java.util.*;

/**
 * BST implementation.
 */
public class BSTImpl {

  static class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
      this.data = data;
    }
  }

  static Node insert(Node node, int data) {
    if (node == null) {
      return new Node(data);
    }

    if (data < node.data) {
      node.left = insert(node.left, data);
    } else {
      node.right = insert(node.right, data);
    }
    return node;
  }

  static boolean search(Node node, int data) {
    if (node == null) {
      return false;
    }
    if (data < node.data) {
      return search(node.left, data);
    } else if (data > node.data) {
      return search(node.right, data);
    }
    return true;
  }

  static int bSTImpl(String str) {
    return 0;
  }

  public static void main(String args[]) {
    Node tree = runSample(new int[]{9, 6, 3, 8, 18, 15, 16});
    runSearch(tree, 9);
    runSearch(tree, 6);
    runSearch(tree, 3);
    runSearch(tree, 8);
    runSearch(tree, 18);
    runSearch(tree, 15);
    runSearch(tree, 16);
    runSearch(tree, 2);
    runSearch(tree, 19);
    runSearch(tree, 14);
  }

  static Node runSample(int[] nums) {
    Node node = null;
    for (int n : nums) {
      node = insert(node, n);
    }
    printTree(node);
    printTreeInOrder(node);
    return node;
  }

  static void runSearch(Node tree, int data) {
    System.out.printf("%s? %s\n", data, search(tree, data));
  }

  static void printTree(Node head) {
    List<Node> ls = new ArrayList<>();
    List<Node> ls2 = new ArrayList<>();

    if (head == null) {
      return;
    }
    ls.add(head);

    while (!ls.isEmpty()) {
      for (Node n : ls) {
        System.out.print(n.data + " ");
        if (n.left != null) {
          ls2.add(n.left);
        }
        if (n.right != null) {
          ls2.add(n.right);
        }
      }
      System.out.println();

      ls.clear();
      List<Node> tmp = ls;
      ls = ls2;
      ls2 = tmp;
    }
  }

  static void printTreeInOrder(Node node) {
    printTreeInOrderHelper(node);
    System.out.println();
  }

  static void printTreeInOrderHelper(Node node) {
    if (node == null) {
      return;
    }

    printTreeInOrderHelper(node.left);
    System.out.print(node.data + " ");
    printTreeInOrderHelper(node.right);
  }
}

@@ -726,32 +726,1055 @@
 turn true;%0A  %7D%0A%0A
+  static Node remove(Node node, int data) %7B%0A    if (node == null) %7B%0A      return null;%0A    %7D%0A    if (data %3C node.data) %7B%0A      node.left = remove(node.left, data);%0A    %7D else if (data %3E node.data) %7B%0A      node.right = remove(node.right, data);%0A%0A    %7D else %7B%0A      // we found the value in this node, so remove this node%0A      if (node.left == null && node.right == null) %7B%0A        return null;%0A      %7D%0A      if (node.left == null) %7B%0A        return node.right;%0A      %7D%0A      if (node.right == null) %7B%0A        return node.left;%0A      %7D%0A%0A      // replace this node's value with the smallest of the right, remove%0A      // that node, then return the current node%0A      node.right = replaceSmallestAndRemove(node.right, node);%0A    %7D%0A    return node;%0A  %7D%0A%0A  static Node replaceSmallestAndRemove(Node node, Node originalNode) %7B%0A    if (node.left != null) %7B%0A      node.left = replaceSmallestAndRemove(node.left, originalNode);%0A      return node;%0A    %7D else %7B%0A      originalNode.data = node.data;%0A      return node.right;%0A    %7D%0A  %7D%0A%0A
   static int bST
@@ -1788,24 +1788,24 @@
 ring str) %7B%0A
-
     return 0
@@ -2160,16 +2160,80 @@
 ee, 14);
+%0A%0A    tree = runRemove(tree, 15);%0A    tree = runRemove(tree, 6);
 %0A  %7D%0A%0A  
@@ -2465,24 +2465,24 @@
 int data) %7B%0A
-
     System.o
@@ -2527,32 +2527,223 @@
 e, data));%0A  %7D%0A%0A
+  static Node runRemove(Node tree, int data) %7B%0A    tree = remove(tree, data);%0A    System.out.println(%22remove %22 + data);%0A    printTree(tree);%0A    printTreeInOrder(tree);%0A    return tree;%0A  %7D%0A%0A
   static void pr

implement remove