@@ -0,0 +1,2093 @@
+// Solution to the problem of converting binary search tree into doubly linked list%0A// CTCI 17.12%0Apublic class Tree2List %7B%0A  public static class BiNode %7B%0A    int value;%0A    BiNode node1;%0A    BiNode node2;%0A%0A    public BiNode(int value, BiNode node1, BiNode node2) %7B%0A      this.value = value;%0A      this.node1 = node1;%0A      this.node2 = node2;%0A    %7D%0A%0A    @Override%0A    public String toString() %7B%0A      return %22%5B%22 + this.value + %22%5D%22;%0A    %7D%0A  %7D%0A%0A  public static class Segment %7B%0A    BiNode head;%0A    BiNode tail;%0A  %7D%0A%0A  // Convert tree to list (tree is BST, list is doubly linked list)%0A  public static BiNode tree2list(BiNode root) %7B%0A    if (root == null) return null;%0A    Segment seg = convert(root);%0A    return seg.head;%0A  %7D%0A%0A  static Segment convert(BiNode root) %7B%0A    if (root == null) return null;%0A    Segment left = convert(root.node1);%0A    Segment right = convert(root.node2);%0A    Segment curr = new Segment();%0A%0A    if (left == null) %7B%0A      root.node1 = null;%0A      curr.head = root;%0A    %7D else %7B%0A      root.node1 = left.tail;%0A      left.tail.node2 = root;%0A      curr.head = left.head;%0A    %7D%0A%0A    if (right == null) %7B%0A      root.node2 = null;%0A      curr.tail = root;%0A    %7D else %7B%0A      root.node2 = right.head;%0A      right.head.node1 = root;%0A      curr.tail = right.tail;%0A    %7D%0A%0A    return curr;%0A  %7D%0A%0A  // == Testing ==%0A%0A  public static void solution(int%5B%5D arr) %7B%0A    java.util.Arrays.sort(arr);%0A    BiNode bst = bst(arr, 0, arr.length - 1);%0A    BiNode list = tree2list(bst);%0A    System.out.println(%22List from left to right:%22);%0A    BiNode tmp = list;%0A    while (tmp != null) %7B%0A      System.out.println(tmp);%0A      tmp = tmp.node2;%0A    %7D%0A    tmp = list;%0A    while (tmp != null && tmp.node2 != null) %7B%0A      tmp = tmp.node2;%0A    %7D%0A    System.out.println(%22List from right to left:%22);%0A    while (tmp != null) %7B%0A      System.out.println(tmp);%0A      tmp = tmp.node1;%0A    %7D%0A  %7D%0A%0A  private static BiNode bst(int%5B%5D arr, int start, int end) %7B%0A    if (start %3E end) return null;%0A    int mid = (start + end) / 2;%0A    return new BiNode(arr%5Bmid%5D, bst(arr, start, mid - 1), bst(arr, mid + 1, end));%0A  %7D%0A%7D%0A

add solution