# Converting Binary Trees to Doubly Linked Lists for Fun & Profit

As a ‘fresher, let’s define what each data type even is.

A binary tree is a **tree** data structure in which each node has at most two children, which are referred to as the left child and the right child.

A doubly-linked list (DLL) is a linked list where each node contains a reference to the previous node as well as the next node (unless the node is at the head or tail of the list, in the case of non-circular lists).

Given the binary tree below, we should end up with the subsequent DLL.

Looking at the results, it’s clear that the root of the BT is in the middle of the DLL, and all values to the left or right of it are in turn to the left and right of that node. We can say the same thing about the sub-trees and their roots to the left and right of the primary root — the word “recursive” should be flashing over your head right now.

(Note: GeeksforGeeks commenters say this question comes up in final-round interviews at Amazon.)

If you want to work with something a little more concrete, I’ve adapted a simple BT implementation from Java2s.com. That code is below:

function Node(data, left, right) {

this.data = data;

this.left = left;

this.right = right;

this.show = show;

}

function show() {

return this.data;

}function Node(value, left, right) {

this.value = value;

this.left = left;

this.right = right;

this.show = show;

}

function show() {

return this.value;

}var root = new Node(10);

root.left = new Node(12);

root.left.left = new Node(25);

root.left.right = new Node(30);

root.right = new Node(15);

root.right.left = new Node(36);

Once you’ve read and re-read the above guidelines, minimize your browser and try it yourself! I’m giving myself 20 minutes to implement a JavaScript solution. (Wish me luck…)

…

…

At time, I ended up with the following code:

function convertBinaryTreeToDLL(root, headingLeft) {

var leftChild = root.left;

var rightChild = root.right; var inorderPredecessor;

if (headingLeft) {

inorderPredecessor = rightChild;

} else {

inorderPredecessor = leftChild;

}; if (leftChild && (leftChild.left || leftChild.right)) {

convertBinaryTreeToDLL(leftChild, true);

} if (rightChild && (rightChild.left || rightChild.right)) {

convertBinaryTreeToDLL(rightChild, false);

} var rootDLL;

if (noFurtherSubtrees(root)) {

rootDLL = new DLLNode(root.value);

if (leftChild) {

rootDLL.previous = new DLLNode(leftChild.value);

}

if (rightChild) {

rootDll.next = new DLLNode(rightChild.value);

}

} return rootDLL}function noFurtherSubtrees(root) {

var leftChild = root.left;

var rightChild = root.right; if (leftChild) {

if (leftChild.left || leftChild.right) return false;

}

if (rightChild) {

if (rightChild.left || rightChild.right) return false;

}

return true

}

Okay, clearly I fail. The main problem with my solution is that the recursive call does not work quite right. The function expects the BT root node to be passed in, but that root node has no parent, so which boolean value should we pass to the function? Similarly, the recursion currently has no way of putting the DLLNodes together.

A working JavaScript implementation comes from Stack Overflow user csander (the actual conversion function is at the very end):

function TreeNode(left, value, right) {

this.value = value;

this.left = left;

this.right = right;

}function ListNode(prev, value, next) {

this.prev = prev;

this.value = value;

this.next = next;

}var tree = new TreeNode(

new TreeNode(

new TreeNode(null, 25, null),

12,

new TreeNode(null, 30, null)

),

10,

new TreeNode(

new TreeNode(null, 36, null),

15,

null

)

);function LinkedList(head, tail) {

if (tail === undefined) tail = head;

this.head = head;

this.tail = tail;

}LinkedList.prototype.addToStart = function(list) {

this.head.prev = list.tail;

list.tail.next = this.head;

this.head = list.head;

}LinkedList.prototype.addToEnd = function(list) {

this.tail.next = list.head;

list.head.prev = this.tail;

this.tail = list.tail;

};function bstToLL(tree) {

var centerNode = new ListNode(null, tree.value, null);

var list = new LinkedList(centerNode);

if (tree.left) list.addToStart(bstToLL(tree.left));

if (tree.right) list.addToEnd(bstToLL(tree.right));

return list;

}var linkedList = bstToLL(tree);

for (var node = linkedList.head; node; node = node.next) console.log(node.value);

What differences do we see between the general idea behind my version v. csander’s? I’ve noted a couple below:

- My function expects to be passed the head of the tree; theirs expects the entire tree and takes advantage of the tree’s head property.
- My function is less modular; theirs chooses to delegate addToStart and addToEnd to the LinkedList constructor object as methods.

I think a good principle behind csanders’ design is that recursive functions are best when they’re really skinny, and when the recursive calls happen to add to an already-existing item, rather than return an item they themselves create.

Kudos to any of you who got this right.