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





    ReplyDelete