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.

public class Node {

ReplyDeletepublic 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! :)