## Sunday, September 23, 2012

### Convert a BST into a double linked list

preserving the order

#### 1 comment:

1. public class Node {
public Node left, right, next, prev;
}

int MIN = 0;
int MAX = 1;
public static Node bstToList(Node n, int minOrMax) {

if (n == null) return null;

Node maxMin = bstToList(n.left, MAX);
Node minMax = bstToList(n.right, MIN);

if (maxMin != null) {
maxMin.next = n;
n.prev = maxMin;
}

if (minMax != null) {
n.next = minMax;
minMax.prev = n;
}

if (minOrMax == MAX) return findMax(n);
if (minOrMax == MIN) return findMin(n);

}

public static void main() {
Node root = generateBST();
Node head = bstToList(root, MIN);
}

The methods findMax and findMin simply scan the input list rightward or leftward (respectively) in order to find the absolute Max or Min.

This implementation seems to be O(n^2) due to findMin/Max functions. I think it is easy to keep track of the abs. min and max and transform the whole algo in a O(n) solution.

As further note, I could have used the "left" and "right" pointers to keep track of the next and prev elements in the double liked list. In this case I would have literally changed the BST to a double linked list.
But this way I think the implementation is clearer and I preserve the BST structure as well as the double linked list.

Hope this works! :)