// Solution to the problem of converting binary search tree into doubly linked list
// CTCI 17.12
public class Tree2List {
  public static class BiNode {
    int value;
    BiNode node1;
    BiNode node2;

    public BiNode(int value, BiNode node1, BiNode node2) {
      this.value = value;
      this.node1 = node1;
      this.node2 = node2;
    }

    @Override
    public String toString() {
      return "[" + this.value + "]";
    }
  }

  public static class Segment {
    BiNode head;
    BiNode tail;
  }

  // Convert tree to list (tree is BST, list is doubly linked list)
  public static BiNode tree2list(BiNode root) {
    if (root == null) return null;
    Segment seg = convert(root);
    return seg.head;
  }

  static Segment convert(BiNode root) {
    if (root == null) return null;
    Segment left = convert(root.node1);
    Segment right = convert(root.node2);
    Segment curr = new Segment();

    if (left == null) {
      root.node1 = null;
      curr.head = root;
    } else {
      root.node1 = left.tail;
      left.tail.node2 = root;
      curr.head = left.head;
    }

    if (right == null) {
      root.node2 = null;
      curr.tail = root;
    } else {
      root.node2 = right.head;
      right.head.node1 = root;
      curr.tail = right.tail;
    }

    return curr;
  }

  // == Testing ==

  public static void solution(int[] arr) {
    java.util.Arrays.sort(arr);
    BiNode bst = bst(arr, 0, arr.length - 1);
    BiNode list = tree2list(bst);
    System.out.println("List from left to right:");
    BiNode tmp = list;
    while (tmp != null) {
      System.out.println(tmp);
      tmp = tmp.node2;
    }
    tmp = list;
    while (tmp != null && tmp.node2 != null) {
      tmp = tmp.node2;
    }
    System.out.println("List from right to left:");
    while (tmp != null) {
      System.out.println(tmp);
      tmp = tmp.node1;
    }
  }

  private static BiNode bst(int[] arr, int start, int end) {
    if (start > end) return null;
    int mid = (start + end) / 2;
    return new BiNode(arr[mid], bst(arr, start, mid - 1), bst(arr, mid + 1, end));
  }
}

@@ -1294,24 +1294,650 @@
  curr;%0A  %7D%0A%0A
+  public static BiNode tree2list2(BiNode root) %7B%0A    convert2(null, root, null);%0A    while (root != null && root.node1 != null) %7B%0A      root = root.node1;%0A    %7D%0A    return root;%0A  %7D%0A%0A  public static void convert2(BiNode left, BiNode root, BiNode right) %7B%0A    if (root == null) return;%0A    BiNode node1 = root.node1;%0A    if (root.node1 == null && left != null) %7B%0A      root.node1 = left;%0A      left.node2 = root;%0A    %7D%0A    BiNode node2 = root.node2;%0A    if (root.node2 == null && right != null) %7B%0A      root.node2 = right;%0A      right.node1 = root;%0A    %7D%0A    convert2(left, node1, root);%0A    convert2(root, node2, right);%0A  %7D%0A%0A
   // == Test
@@ -1943,16 +1943,16 @@
 ting ==%0A
-
 %0A  publi
@@ -2096,14 +2096,28 @@
 list
+2
 (bst);
+ // tree2list
 %0A   

add method with no additional data structures