Convert BST to Double Linked List

Facebook Interview Yahoo Interview Tree DFS

Convert a binary search tree to a double linked list.

to

Solution

The first thing to consider is: do we need to construct a new linked list?
Not necessarily. If you understand the tree and linked list structure well enough, the answer should be clear.
Since a tree node

class TreeNode {
    …
    TreeNode left;
    TreeNode right;
}

has the exact same number of pointers as a double linked list node

class ListNode {
    …
    ListNode prev;
    ListNode next;
}

It is best for us to do the conversion in place. Take node.left as a prev pointer and node.right as a next pointer.
Now the problem becomes how to change some of the direction of pointers in the tree to convert it to a list.

This can be done easily by Depth First Search.

For every node N in the tree, call recursion to convert n.left and n.right to double linked lists.

List l1 = BSTtoDLL(n.left);
List l2 = BSTtoDLL(n.right);

Then append N to l1, and append l2. This creates a double linked list L that contain every node in N and the left and right subtrees of N.
Return L at last.

Implementation

public class BSTtoDLL {

    class TreeNode {
        int val;
            TreeNode left;
            TreeNode right;
    }
    
    public TreeNode[] BSTtoDLL (TreeNode root) {
        if(root == null) return null;
        TreeNode[] prev = BSTtoDLL(root.left);  //DLL of left subtree
        TreeNode[] next = BSTtoDLL(root.right); //DLL of right subtree

        TreeNode[] res = new TreeNode[] {root, root};
        if(prev != null) {
            prev[1].right = root; //append root to tail of prev list
            root.left = prev[1];
            res[0] = prev[0];
        }
        if(next != null) {
            next[0].left = root; //append head of next list to root
            root.right = next[0];
            res[1] = next[1];
        }
        return res;
    }
}