Поисковое дерево с возрастающими значениям

Задача. Дано бинарное поисковое дерево. Реорганизовать его в порядке in_order таким образом, чтобы самый левый (наименьший, поскольку это бинарное поисковое дерево) ребенок стал корнем, чтобы у любой вершины не было левого ребенка, но был только правый ребенок.

Пример:
Дано: [5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

Результат: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9  

Примечания:

1. У каждого вдерева вершин 1 до 100.
2. У каждой вершины значения варьируются от 0 до 1000.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

 Очевидное решение: рекурсивно в глубину (dfs) добираемся до самого левого элемента, записываем его в массив. потом записываем его отца в массив. потом рекурсивно записываем в массив правое поддерево отца.

Затем, на основании массива строи результирующее дерево:

class Solution {
 public TreeNode increasingBST(TreeNode root) {
  List<Integer> vals = new ArrayList();
  dfs(root, vals);
  TreeNode cur = new TreeNode(vals.get(0));
// построили массив vals -> теперь строим нужное дерево
  TreeNode result = cur;
  for (int i = 1; i < vals.size(); i++) {
   cur.right = new TreeNode(vals.get(i));
   cur = cur.right;
  }
  return result;
 }

// рекурсивно строим массив: левое поддерево + рассматриваемой крень + правое поддерево
 public void dfs(TreeNode node,  List<Integer> vals) {
  if (node == null) return;
  dfs(node.left, vals);
  vals.add(node.val);
  dfs(node.right, vals);
 }
}

Идея решения:
Определение порядка in_order:
result = inorder(root.left) + root + inorder(root.right) 

То есть сначала делаем обход (рекурсивно) левого поддерева, потом корень, потом (рекурсивно) правое поддерево. 

Рекурсивно вызываем функцию increasingBST(TreeNode node, TreeNode tail), где tail -это следующая вершина в порядке in-order (может быть корень или корень правого поддерева).

Если node == null, голова списка будет tail, и мы сразу возвращаем tail.

Мы рекурсивно вызваем вызываем increasingBST(node.left, root), и меняем левое поддерево в связный список + текущая вершина (локальный root), поскольку текущая вершина больше всех элементов в левом поддереве (по свойству бинарного поисковог дерева).

Мы рекурсивно вызваемincreasingBST(node.right, tail), и меняем правое поддерево в связный лист + tail.

Теперь результат будет в формате связного списка, где каждый следующий элемент - это правый ребенок текущего элемента.
И root.left = null.

Результат описывается формулой: 

increasingBST(root.left) + root + increasingBST(root.right).
Рассмотрим, например вызов increasingBST(3, 5).
Будет реогранизовано левое поддерево в вершине 3, так чтобы получилась цепочка 1->2->3. Причём res=1,
3.left = null.
3.right=4 (и т.д. правое поддерево, если бы оно было). То есть 3->4->... если бы у 4 было поддерево.
И самый правый элемент поддерева в 3 (то есть 4) рано или поздно укажет на 5 в строке node.right=..., потому что tail будет передаваться рекурсивно по правому поддереву, как вершина, к которой "подцепиться". И 4 укажет на 5, поскольку исчерпает свои поддеревья.

Анализ алгоритма

O(N) чтобы обойти все  N вершин исходного дерева.
O(height) - то есть, высота дерева, столько памяти нужно.

Компилируемое решение:

public TreeNode increasingBST(TreeNode root) {
        return increasingBST(root, null);
    }

    public TreeNode increasingBST(TreeNode node, TreeNode tail) {
        if (root == null) return tail;
        TreeNode res = increasingBST(node.left, node);
// реорганизуем левое поддерево и добавим ему в хвост текущую вершину node
        node.left = null;
// левое поддерево у текущей вершины более не существует
        node.right = increasingBST(node.right, tail);
// реорганизуем правое поддерево
        return res;
    }