Does this algorithm for converting a Binary Search Tree into a sorted linked list on Wikipedia have a bug in it?

Question

I wanted to get a sanity check here. I believe the algorithm listed on the wikipedia page for the Day–Stout–Warren algorithm for balancing BSTs has a problem.

This pseudocode purports to turn a BST into a "vine" (lined list).

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

The problem is the algorithm skips over the left node of the root node. So if you start with a root node with two child nodes, you end up with a LL that loses the left subtree of the root node if it exists.

I think this fixes it, though inelegantly. It basically shifts tail and rest up one level each, and adds a head variable to remember the lowest value which is the head of the list.

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

I created a java function to test it out. (I also created a java version of the flawed algorithm to confirm it was indeed dropping the left subtree of the root node).

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;
    }

I tested it with this before and after the fix to confirm the original didn't work and my updated version does:

        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));

Please let me know if I missed anything.

Answer 1

The problem is the algoright skips over the left node of the root node. So if you start with a root node with two child nodes, you end up with a LL that loses the left subtree of the root node if it exists.

This isn't a problem, because the tree-to-vine subroutine is not called on the actual root node. Steps 1 and 2 of the algorithm given on the page you're reading are

1. Allocate a node, the "pseudo-root", and make the tree's actual root the right child of the pseudo-root.
2. Call tree-to-vine with the pseudo-root as its argument.

This is the only use of the tree-to-vine subroutine. The pseudo-root has no left child, so it's fine that tree-to-vine never tries to look at the pseudo-root's left child.