Есть ли в этом алгоритме преобразования двоичного дерева поиска в отсортированный связанный список в Википедии ошибка?

Я хотел пройти здесь проверку на вменяемость. Я считаю, что алгоритм, указанный на странице Википедии для алгоритма Дэй-Стаут-Уоррен для балансировки BST, имеет проблему.

Этот псевдокод призван превратить BST в «лозу» (выровненный список).

routine tree-to-vine(root)
    // Convert tree to a "vine", i.e., a sorted linked list,
    // using the right pointers to point to the next node in the list
    tail ← root
    rest ← tail.right
    while rest ≠ nil
        if rest.left = nil
            tail ← rest
            rest ← rest.right
        else
            temp ← rest.left
            rest.left ← temp.right
            temp.right ← rest
            rest ← temp
            tail.right ← temp

Проблема в том, что алгоритм пропускает левый узел корневого узла. Таким образом, если вы начнете с корневого узла с двумя дочерними узлами, вы получите LL, который теряет левое поддерево корневого узла, если оно существует.

Я думаю, что это исправляет ситуацию, хотя и неэлегантно. По сути, он сдвигает tail и rest на один уровень вверх каждый и добавляет переменную head для запоминания наименьшего значения, которое является главой списка.

routine tree-to-vine-fixed(root)
    head ← null
    tail ← null
    rest ← root

    while rest ≠ null
        if rest.left = null
            if tail = null
                // Set head to the minimum value of the tree (left-most node)
                head ← rest
            // No left child, move the tail and rest pointers forward
            tail ← rest
            rest ← rest.right
        else
            // Left child exists, perform rotations
            temp ← rest.left
            rest.left ← temp.right
            temp.right ← rest
            rest ← temp
            if tail ≠ null
                tail.right ← temp

    return head

Я создал функцию Java, чтобы проверить ее. (Я также создал Java-версию ошибочного алгоритма, чтобы убедиться, что он действительно удаляет левое поддерево корневого узла).

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
public class DSW {
    public static TreeNode treeToVineFixed(TreeNode root) {
        TreeNode head = null, tail = null;  // ** change: shift tail and rest up
        TreeNode rest = root;

        while (rest != null) {
            if (rest.left == null) {
                if (tail == null)  // ** change: set the head to be the min value of the tree, i.e. left-most path
                    head = rest;
                // No left child, move the tail and rest pointers forward
                tail = rest;
                rest = rest.right;
            } else {
                // Left child exists, perform rotations
                TreeNode temp = rest.left;
                rest.left = temp.right;
                temp.right = rest;
                rest = temp;
                if (tail != null)  // **change: otherwise NPE
                    tail.right = temp;
            }
        }
        return head;
    }

Я протестировал его до и после исправления, чтобы убедиться, что оригинал не работает, а моя обновленная версия работает:

        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(10);
        root.right.left = new TreeNode(8);
        root.right.right = new TreeNode(20);
        root.right.left.left = new TreeNode(7);
        root.right.left.right = new TreeNode(9);

        System.out.println("Original Tree");
        System.out.println(renderAsciiTree(root));

        var head = treeToVineOriginal(root);  // not shown
        System.out.println("Incorrect Vine");
        System.out.println(renderAsciiTree(head));

        var head = treeToVineFixed(root);
        System.out.println("Vine");
        System.out.println(renderAsciiTree(head));

Пожалуйста, дайте мне знать, если я что-то пропустил.