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.
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
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.