24.20 Convert a sorted Doubly Linked List into a BST


#1

Problem 24.20 Pg.407 in EPI (Java) asks to reuse the doubly linked list for BST using previous and next fields for the left and right children respectively. However, in the solution it looks like the node references are not being updated, rather they are assigned new address. Is this a typo or am I missing something: (I have attached the code snippet from the book below and my fix to solve the problem with the given constraints).

Thanks!

In the book:

private static DoublyLinkedListNode < Integer > buildSortedListHelper(int start, int end) {
    if (start >= end) {
        return;
    }
    
    int mid = start + (end-start) / 2;
    // possible voilation of problem constraint below as this will assign a new address to the nodes rather than reusing them
    DoublyLinkedListNode cur = new DoublyLinkedListNode<>(head.data, left, null);
    
    head = head.next;
    cur.next = buildSortedListHelper(mid+1, end);
    return cur;

}

My fix to the code:

private static DoublyLinkedListNode < Integer > buildSortedListHelper(int start, int end) {
    if (start >= end) {
        return;
    }
    
    int mid = start + (end-start) / 2;
    // my fix to satisfy the constraint
    DoublyLinkedListNode cur = head;
    cur.left = left;
    
    head = head.next;
    cur.next = buildSortedListHelper(mid+1, end);
    return cur;

}

For reference purposes:

private static DoublyLinkedListNode head;

public static DoublyLinkedListNode buildBSTFromSortedList(DoublyLinkedListNode L, int length){
    head = L;
    return buildSortedListHelper(0, length);
}


#2

I haven’t worked on this problem yet, but you could try running the book code against the tests in the EPI judge and see if they pass.


#3

Hi @testUser,

Yours won’t work since cur is just a reference to head and it will change as head moves. That is the reason we explicitly new a node here. You can try this in our judge framework for sure.


#4

Ok, but isn’t there a problem in the solution then? We’re supposed to be reusing the nodes, not allocating new ones.