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